{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Best Time to Buy and Sell Stock IV"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxProfit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #买卖股票的最佳时机 IV"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>prices</code> 和一个整数 <code>k</code> ，其中 <code>prices[i]</code> 是某支给定的股票在第 <code>i</code><em> </em>天的价格。</p>\n",
    "\n",
    "<p>设计一个算法来计算你所能获取的最大利润。你最多可以完成 <code>k</code> 笔交易。也就是说，你最多可以买 <code>k</code> 次，卖 <code>k</code> 次。</p>\n",
    "\n",
    "<p><strong>注意：</strong>你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>k = 2, prices = [2,4,1]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>k = 2, prices = [3,2,6,5,0,3]\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。\n",
    "     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= prices.length &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= prices[i] &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [best-time-to-buy-and-sell-stock-iv](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [best-time-to-buy-and-sell-stock-iv](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n[2,4,1]', '2\\n[3,2,6,5,0,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        #find all increase interval\n",
    "        if len(prices) == 0 or len(prices) == 1:\n",
    "            return 0\n",
    "        \n",
    "        buy_pt = 0\n",
    "        sell_pt = 0\n",
    "        total = 0\n",
    "        for i in range(1, len(prices)):\n",
    "            if prices[i-1] <= prices[i]:\n",
    "                sell_pt = i\n",
    "                if buy_pt is None:\n",
    "                    buy_pt = i - 1\n",
    "            else:\n",
    "                if buy_pt is not None:\n",
    "                    total += prices[sell_pt] - prices[buy_pt]\n",
    "                    buy_pt = None\n",
    "                    sell_pt = None\n",
    "        if buy_pt is not None:\n",
    "            total += prices[sell_pt] - prices[buy_pt]\n",
    "        return total\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not prices:\n",
    "            return 0\n",
    "        result=0\n",
    "        for i in range(1,len(prices)):\n",
    "            if prices[i]>prices[i-1]:\n",
    "                result+=(prices[i]-prices[i-1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not len(prices):\n",
    "            return 0\n",
    "        prices.append(0)\n",
    "        minPrice = float('inf')\n",
    "        lastPrice = prices[0]\n",
    "        sumProfit = 0\n",
    "        for  price in prices:\n",
    "            if lastPrice>price:\n",
    "                minPrice = price\n",
    "                sumProfit += lastProfit\n",
    "            minPrice = min(minPrice,price)\n",
    "            profit = price - minPrice\n",
    "            lastProfit = profit\n",
    "            lastPrice = price\n",
    "        return sumProfit\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: 'List[int]') -> 'int':\n",
    "        l = len(prices)\n",
    "        if l == 0 or l == 1:\n",
    "            return 0\n",
    "        result = [0] * l\n",
    "        m = [0] * l\n",
    "        m[0] = 7\n",
    "        temp = prices[0]\n",
    "        for i in range(1, l):\n",
    "            if temp >= prices[i]:\n",
    "                result[i] = result[i-1]\n",
    "                temp = min(temp, prices[i])\n",
    "                continue\n",
    "            m[i-1] = prices[i-1]\n",
    "            for h in range(i-1, -1, -1):\n",
    "                m[h] = min(m[i-1],m[h])\n",
    "                if m[h] == temp:\n",
    "                    result[i] = max(result[i], result[i-1], prices[i]-temp + (result[h-1] if h > 0 else 0))\n",
    "                    break\n",
    "                elif m[h] >= prices[i]:\n",
    "                    continue\n",
    "                else:\n",
    "                    if m[h] < prices[i]:\n",
    "                        result[i] = max(result[i], result[i-1], prices[i]-m[h]+ (result[h-1] if h > 0 else 0) )\n",
    "            temp = min(temp, prices[i])\n",
    "        return result[l-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if prices == []:\n",
    "            return 0\n",
    "        cash = 0\n",
    "        hold = -prices[0]\n",
    "        \n",
    "        for i in prices:\n",
    "            cash = max(cash,hold + i)\n",
    "            hold = max(hold,cash-i)\n",
    "        return cash"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        i=0\n",
    "        tmp = 0\n",
    "        while i<len(prices)-1:\n",
    "            if prices[i] >=prices[i+1]:\n",
    "                a=0\n",
    "            else:\n",
    "                a=prices[i+1]-prices[i]\n",
    "            tmp += a\n",
    "            i += 1\n",
    "        return tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        profit = 0\n",
    "        for i in range(0, len(prices)-1):\n",
    "            if prices[i+1] > prices[i]:\n",
    "                profit += prices[i+1] - prices[i]\n",
    "        return profit\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(prices);\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        s0, s1, s2 = 0, -prices[0], -prices[0]\n",
    "        \n",
    "        for i in range(n):\n",
    "            s0, s1, s2 = max(s0, s2), max(max(s0 - prices[i], s1), s2 - prices[i]), s1 + prices[i]\n",
    "        \n",
    "        return max(s0, s2);\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        result = 0\n",
    "        for i in range(0, len(prices)):\n",
    "            if i+1 < len(prices):\n",
    "                if prices[i+1] >= prices[i]:\n",
    "                    print(prices[i+1],prices[i])\n",
    "                    result += (prices[i+1] - prices[i])\n",
    "        return result \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(prices)<2:\n",
    "            return 0\n",
    "        \n",
    "        benefit = 0\n",
    "        buy_sold = []\n",
    "        for i in range(len(prices)-1):\n",
    "            if prices[i] < prices[i+1] and len(buy_sold) == 0:\n",
    "                buy_sold.append(prices[i])\n",
    "            if prices[i] > prices[i+1] and len(buy_sold) == 1:\n",
    "                benefit += prices[i]-buy_sold.pop()\n",
    "            print(buy_sold)\n",
    "        if len(buy_sold) == 1:\n",
    "            benefit += prices[-1]-buy_sold.pop()\n",
    "                \n",
    "        return benefit\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if prices==[]:\n",
    "            return 0\n",
    "        l = len(prices)\n",
    "        buy  = 0\n",
    "        sell = 1\n",
    "        now = 0\n",
    "        last = prices[0]\n",
    "        buyp = 0\n",
    "        earn =0\n",
    "        for i in range(1,l):\n",
    "            print(prices[i])\n",
    "            if prices[i-1]<prices[i] and buy == 0 :\n",
    "                print(\"buy\")\n",
    "                buy =1\n",
    "                buyp = prices[i-1]\n",
    "            if  prices[i-1]>prices[i] and buy ==1:\n",
    "                print(\"sell\")\n",
    "                buy = 0\n",
    "                earn += prices[i-1] - buyp\n",
    "            if buy ==1 and i == l-1:\n",
    "                print(\"sell\")\n",
    "                buy = 0\n",
    "                earn += prices[i] - buyp\n",
    "        return earn\n",
    "                \n",
    "                \n",
    "#             now = prices[i]\n",
    "#             print(now)\n",
    "#             if buy ==0 and sell ==1 and now <last:\n",
    "#                 print(\"buy\")\n",
    "#                 buy =1\n",
    "#                 buyp = now\n",
    "#                 sell = 0\n",
    "                \n",
    "#             if buy ==1 and (sell ==0 or i ==l-1)and buyp <now :\n",
    "#                 print(\"sell\")\n",
    "#                 sell =1\n",
    "#                 earn += now-buyp\n",
    "#                 buy = 0 \n",
    "        # return earn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not prices:return 0\n",
    "        dp = [[0]*2 for _ in range(len(prices))]\n",
    "        dp[0][0], dp[0][1] = 0, -prices[0]\n",
    "        for i in range(1, len(prices)):\n",
    "            dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])\n",
    "            dp[i][1] = max(dp[i-1][0]-prices[i], dp[i-1][1])\n",
    "        return dp[-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not prices:\n",
    "            return 0\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        profit = [[0 for _ in range(2)] for _ in range(len(prices))]\n",
    "\n",
    "        # 0 未购买 1 已持有\n",
    "        profit[0][0], profit[0][1] = 0, -prices[0]\n",
    "\n",
    "        for i in range(1, len(prices)):\n",
    "            profit[i][0] = max(profit[i - 1][0], profit[i - 1][1] + prices[i])\n",
    "            profit[i][1] = max(profit[i - 1][1], profit[i - 1][0] - prices[i])\n",
    "            res = max(res, profit[i][0], profit[i][1])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        profit0 = 0\n",
    "        profit1 = - max(prices) - 100 if len(prices) > 0 else -100\n",
    "        for price in prices:\n",
    "            p0 = max(profit0, profit1 + price)\n",
    "            p1 = max(profit1, profit0 - price)\n",
    "            profit0 = p0\n",
    "            profit1 = p1\n",
    "        return profit0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: 'List[int]') -> 'int':\n",
    "        if len(prices) == 0:\n",
    "            return 0\n",
    "        profit = 0\n",
    "        current = prices[0]\n",
    "        for i in range(1, len(prices)):\n",
    "            if prices[i] < prices[i - 1]:\n",
    "                profit += (prices[i - 1] - current)\n",
    "                current = prices[i]\n",
    "        profit += (prices[-1] - current)\n",
    "        return profit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: 'List[int]') -> 'int':\n",
    "        ben = 0\n",
    "        for i in range(len(prices)-1):\n",
    "            if prices[i]<prices[i+1]:\n",
    "                ben+=prices[i+1]-prices[i]\n",
    "        return ben"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        if prices == []: return 0\n",
    "\n",
    "        m = 0  # 累计利润\n",
    "        for i in range(1, len(prices)):\n",
    "            res = prices[i] - prices[i-1]\n",
    "            if res > 0:\n",
    "                m += res\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        if not len(prices):\n",
    "            return 0\n",
    "        max_profit = 0\n",
    "        for index in range(1,len(prices)):\n",
    "            if prices[index] >= prices[index-1]:\n",
    "                max_profit += (prices[index] - prices[index - 1])\n",
    "        return max_profit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        if len(prices) == 0:\n",
    "            return 0\n",
    "        tmp = prices[0]\n",
    "        sum = 0\n",
    "        for index in range(1, len(prices)):\n",
    "            if prices[index] > tmp:\n",
    "                sum += prices[index] - tmp\n",
    "                tmp =  prices[index]\n",
    "            else:\n",
    "                tmp = prices[index]\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        if n < 2:\n",
    "            return 0\n",
    "        dp_i_0, dp_i_1 = 0, -float('inf')\n",
    "        for i in range(n):\n",
    "            temp = dp_i_0\n",
    "            dp_i_0 = max(dp_i_0, dp_i_1 + prices[i])\n",
    "            dp_i_1 = max(dp_i_1, temp - prices[i])\n",
    "        return dp_i_0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(1, len(prices)):\n",
    "            earned = prices[i] - prices[i - 1]\n",
    "            if earned > 0:\n",
    "                res += earned\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, lstPrice: List[int]) -> int:\n",
    "        iSum = 0\n",
    "        iBuy = -1\n",
    "        for iDay in range(len(lstPrice) - 1):\n",
    "            if lstPrice[iDay] < lstPrice[iDay + 1]:\n",
    "                if iBuy < 0:\n",
    "                    iBuy = lstPrice[iDay]\n",
    "                    continue\n",
    "            else:\n",
    "                if iBuy >= 0:\n",
    "                    iSum += lstPrice[iDay] - iBuy\n",
    "                    iBuy = -1\n",
    "        # print(iSum)\n",
    "            # if lstPrice[iDay] > lstPrice[iDay + 1]:\n",
    "            # \tiBuy = iYesterday\n",
    "        if iBuy >= 0:\n",
    "            iSum += lstPrice[-1] - iBuy\n",
    "        return iSum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(1, len(prices)):\n",
    "            if prices[i] > prices[i-1]:\n",
    "                res += prices[i] - prices[i-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        profit = 0\n",
    "        for i in range(1, len(prices)):\n",
    "            tmp = prices[i] - prices[i - 1]\n",
    "            if tmp > 0: profit += tmp\n",
    "        return profit\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        iSum = 0\n",
    "        for iDay in range(len(prices) - 1):\n",
    "            if prices[iDay + 1] > prices[iDay]:\n",
    "                iSum += prices[iDay + 1] - prices[iDay]\n",
    "        return iSum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        result = 0\n",
    "        for i in range(1, len(prices)):\n",
    "            if prices[i] - prices[i-1] > 0:\n",
    "                result += (prices[i] - prices[i-1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        max_profit = 0\n",
    "        for i in range(1, len(prices)):\n",
    "            profit = prices[i] - prices[i-1]\n",
    "            if profit > 0:\n",
    "                max_profit += profit\n",
    "        return max_profit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        buy, sell = -inf, 0\n",
    "        for p in prices:\n",
    "            buy = max(buy, sell - p)\n",
    "            sell = max(sell, buy + p)\n",
    "        return sell"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        ans = 0\n",
    "        d = []\n",
    "        for i in range(1, len(prices)):\n",
    "            d = prices[i] - prices[i - 1]\n",
    "            if d > 0:\n",
    "                ans += d\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        ans = 0\n",
    "        d = []\n",
    "        for i in range(1, len(prices)):\n",
    "            d.append(prices[i] - prices[i - 1])\n",
    "        for x in d:\n",
    "            if x > 0:\n",
    "                ans += x\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "\n",
    "        n=len(prices)\n",
    "        if n==0 or n==1:\n",
    "            return 0\n",
    "        dp1=[0]*n  # sell out on last day\n",
    "        dp2=[0]*n  # buy in on last day\n",
    "        dp2[0]=-prices[0]\n",
    "\n",
    "        for i in range(1,n):\n",
    "\n",
    "            dp1[i]=max(dp1[i-1],dp2[i-1]+prices[i])\n",
    "            dp2[i]=max(dp2[i-1],dp1[i-1]-prices[i])\n",
    "\n",
    "        #print(dp1)\n",
    "        #print(dp2)\n",
    "        return dp1[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        total, index, length = 0, 0, len(prices)\n",
    "        while (index < length):\n",
    "            while (index < length - 1 and prices[index] >= prices[index + 1]):\n",
    "                index += 1\n",
    "            min = prices[index]\n",
    "            while (index < length - 1 and prices[index] <= prices[index + 1]):\n",
    "                index += 1\n",
    "            total += prices[index] - min\n",
    "            index += 1\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        res = 0\n",
    "        n = len(prices)\n",
    "        for i in range(1, n):\n",
    "            res += max(0, prices[i] - prices[i - 1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        l = len(prices)\n",
    "        if l < 2: return 0\n",
    "\n",
    "        res = 0\n",
    "        for i in range(1,l):\n",
    "            profit = prices[i] - prices[i-1]\n",
    "            if profit > 0:\n",
    "                res += profit\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "\n",
    "        stack = [prices[0]]\n",
    "        res = 0\n",
    "        for i in range(1,len(prices)):\n",
    "            if prices[i]>=stack[-1]:\n",
    "                stack.append(prices[i])\n",
    "            else:\n",
    "                if len(stack)>=2:\n",
    "                    res +=stack[-1] -stack[0] \n",
    "                    stack = [prices[i]]\n",
    "                else:\n",
    "                    stack = [prices[i]]\n",
    "        \n",
    "        if len(stack)>=2:\n",
    "            res += stack[-1] -stack[0]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        # 动态规划：第[]天进行操作/不进行操作的最大利润：那也不行，如果状态转移的话怎么知道当前是否持有？\n",
    "        # 第[]天收市的时候持有/不持有时获得的最大利润\n",
    "        dp_array = [[0] * 2] * len(prices)\n",
    "        dp_array[0][0] = -prices[0]\n",
    "        dp_array[0][1] = 0\n",
    "\n",
    "        for i, price in enumerate(prices[1:]):\n",
    "            dp_array[i][0] = max(dp_array[i-1][0], dp_array[i-1][1] - price) # price 总是正数。\n",
    "            dp_array[i][1] = max(price + dp_array[i-1][0] , dp_array[i-1][1]) # 这里是加，因为我们把买设置为负数，如果减去负数就是加上正数了。\n",
    "\n",
    "        return dp_array[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "\n",
    "        n = len(prices)\n",
    "        dp = [[0] * n for i in range(2)]\n",
    "        dp[0][0] = -prices[0]                             # profit\n",
    "\n",
    "        for i in range(1, n):\n",
    "            dp[0][i] = max(dp[0][i - 1], dp[1][i - 1] - prices[i])                           # hold = buy or hold old\n",
    "            dp[1][i] = max(dp[1][i - 1], prices[i] + dp[0][i - 1])                           # do not hold = sell today or do not hold old\n",
    "\n",
    "        # print(dp)\n",
    "        return dp[1][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        buy = [0] * n\n",
    "        sell = [0] * n\n",
    "        buy[0] = -prices[0]\n",
    "        sell[0] = 0\n",
    "        for i in range(1,n):\n",
    "            buy[i] = max(sell[i-1] - prices[i], buy[i-1])\n",
    "            sell[i] = max(buy[i-1] + prices[i], sell[i-1])\n",
    "        print(buy,sell)\n",
    "        return sell[n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "\n",
    "        n = len(prices)\n",
    "        df = [[0] * n for i in range(2)]\n",
    "        df[1][0] = -prices[0]\n",
    "\n",
    "        for i in range(1,n):\n",
    "            df[1][i] = max(df[1][i-1], df[0][i-1] - prices[i])\n",
    "            df[0][i] = max(df[0][i-1], prices[i] + df[1][i-1])\n",
    "        print(df)\n",
    "        return df[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        dp = [0]*len(prices)\n",
    "        for i in range(1, len(prices)+1):\n",
    "            if i == 1:\n",
    "                continue\n",
    "            else:\n",
    "                if prices[-i] >= prices[-i+1]:\n",
    "                    dp[-i] = max(dp[-i], max(dp[-i:]))\n",
    "                else:\n",
    "                    dp_tmp = dp[-i:]\n",
    "                    price_tmp = prices[-i:]\n",
    "                    res = [dp_tmp[k]+price_tmp[k]-prices[-i] for k in range(len(dp_tmp))]\n",
    "                    dp[-i] = max(max(res), dp[-i], max(dp_tmp))\n",
    "        # print(dp)\n",
    "\n",
    "        # cnt = 0\n",
    "        # ans = 0\n",
    "        # for i in dp:\n",
    "        #     if i > 0:\n",
    "        #         ans += i\n",
    "        #         cnt += 1\n",
    "        \n",
    "        # if not cnt:\n",
    "        #     return 0\n",
    "        # else:\n",
    "        #     return ans - cnt + 1\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        # dp = [0]*len(prices)\n",
    "        # for i in range(1,len(prices)):\n",
    "        #     for j in range(i):\n",
    "        #         dp[i] = max([dp[i], dp[j], dp[j-1]+prices[i]-prices[j]])\n",
    "        # return max(dp) \n",
    "\n",
    "        dp = [(0,-prices[0])]\n",
    "        for i in range(1, len(prices)):\n",
    "            dp.append((max(dp[-1][0], dp[-1][1]+prices[i]), max(dp[-1][1], dp[-1][0]-prices[i])))\n",
    "        return max(dp[-1])\n",
    "\n",
    "        # ans = 0\n",
    "        # for i in range(1,len(prices)):\n",
    "        #     ans += max(0, prices[i]-prices[i-1])\n",
    "        # return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices) -> int:\n",
    "        dp = [[0, 0] for i in range(len(prices))]\n",
    "        dp[0] = [-prices[0], 0]\n",
    "        for i in range(1, len(prices)):\n",
    "            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])\n",
    "            dp[i][1] = max(dp[i - 1][0] + prices[i], dp[i - 1][1])\n",
    "        return dp[-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def maxProfit(self, prices: List[int]) -> int:\n",
    "#         profit = 0\n",
    "#         for i in range(1, len(prices)):\n",
    "#             tmp = prices[i] - prices[i - 1]\n",
    "#             if tmp > 0: \n",
    "#                 profit += tmp\n",
    "#         return profit\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        dp = [[0,0] for _ in range(n)]\n",
    "        dp[0] = [-prices[0], 0]\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = max(dp[i-1][0], - prices[i] + dp[i-1][1])\n",
    "            dp[i][1] = max(dp[i-1][1], + prices[i] + dp[i-1][0])\n",
    "        return dp[-1][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        #dp[i][0],dp[i][1]持有与不持有的状态\n",
    "        #dp[i][0] = max(dp[i-1][0],dp[i-1][1]-prices[i])\n",
    "        #dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i])\n",
    "        \n",
    "        length = len(prices)\n",
    "        dp = [[0] * 2 for _ in range(length)]\n",
    "        dp[0][0] = -prices[0]\n",
    "        dp[0][1] = 0\n",
    "        for i in range(1, length):\n",
    "            dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]) \n",
    "            dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])\n",
    "        return dp[-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        N = len(prices)\n",
    "        # 定义状态：dp[i][j]表示在第i天持有或卖出时的最大利润，j=1代表持有，j=0代表卖出\n",
    "        dp = [[0 for j in range(2)] for i in range(N)]\n",
    "\n",
    "        # badcase\n",
    "        for i in range(N):\n",
    "            # badcase\n",
    "            if i - 1 == -1:\n",
    "                dp[i][0] = 0\n",
    "                dp[i][1] = -prices[i]\n",
    "            else:\n",
    "                dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])\n",
    "                dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])\n",
    "        return dp[N-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not prices:\n",
    "            return 0\n",
    "\n",
    "        len_prices = len(prices)\n",
    "        buy1, sell1, buy2, sell2 = -prices[0], 0, -prices[0], 0\n",
    "\n",
    "        for i in range(0, len_prices):\n",
    "            buy1 = max(buy1, -prices[i])\n",
    "            sell1 = max(sell1, buy1 + prices[i])\n",
    "            buy2 = max(buy2, sell1 - prices[i])\n",
    "            sell2 = max(sell2, buy2 + prices[i])\n",
    "\n",
    "        return sell2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(prices)\n",
    "        profit_forward = [0 for i in range(n + 1)]\n",
    "        profit_backward = [0 for i in range(n + 1)]\n",
    "        \n",
    "        # forward\n",
    "        minSoFar = float('inf')\n",
    "        for i in range(n):\n",
    "            if prices[i] < minSoFar:\n",
    "                minSoFar = prices[i]\n",
    "            profit_forward[i + 1] = max(profit_forward[i], prices[i] - minSoFar)\n",
    "        \n",
    "        # backward\n",
    "        maxSoFar = float('-inf')\n",
    "        for i in range(n):\n",
    "            if prices[n - 1 - i] > maxSoFar:\n",
    "                maxSoFar = prices[n - 1 - i]\n",
    "            profit_backward[n - 1 - i] = max(profit_backward[n - i], maxSoFar - prices[n - 1 - i])\n",
    "        \n",
    "        max_profit = 0\n",
    "        for i in range(n + 1):\n",
    "            if profit_forward[i] + profit_backward[i] > max_profit:\n",
    "                max_profit = profit_forward[i] + profit_backward[i]\n",
    "        return max_profit\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        profit_start_point, profit_buy_1, profit_buy_2, profit_sell_1, profit_sell_2 = 0, float('-inf'), float('-inf'), 0, 0\n",
    "        for price in prices:\n",
    "                profit_buy_1 = max(profit_buy_1, profit_start_point - price)\n",
    "                # because -  price, max means spend min\n",
    "                profit_sell_1 = max(profit_sell_1, profit_buy_1 + price)\n",
    "                profit_buy_2 = max(profit_buy_2, profit_sell_1 - price)\n",
    "                # use money based on sell1\n",
    "                profit_sell_2 = max(profit_sell_2, profit_buy_2 + price)\n",
    "                print(profit_buy_1,profit_sell_1,profit_buy_2,profit_sell_2)\n",
    "        return profit_sell_2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        if n <= 0:\n",
    "            return 0\n",
    "        max_k = 2\n",
    "        dp = [[0] * 2 for _ in range(max_k + 1)]\n",
    "        dp[0][0] = 0\n",
    "        for i in range(n):\n",
    "            for k in range(1, max_k + 1):\n",
    "                if i == 0:\n",
    "                    dp[k][0] = 0\n",
    "                    dp[k][1] = -float('INF')\n",
    "                dp[k][0] = max(dp[k][0], dp[k][1] + prices[i])\n",
    "                dp[k][1] = max(dp[k][1], dp[k - 1][0] - prices[i])\n",
    "        return dp[max_k][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        # dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][2][1] + prices[i])\n",
    "        # dp[i][2][1] = max(dp[i-1][2][1], dp[i-1][1][0] - prices[i])\n",
    "        # dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])\n",
    "        # dp[i][1][1] = max(dp[i-1][1][1], -prices[i])\n",
    "\n",
    "        \n",
    "        dp_i10 = 0\n",
    "        dp_i11 = float('-inf') # 只需要存储四个值\n",
    "        dp_i20 = 0\n",
    "        dp_i21 = float('-inf')\n",
    "\n",
    "        for price in prices:\n",
    "            dp_i20 = max(dp_i20, dp_i21 + price) # 第二次操作之后不持股\n",
    "            dp_i21 = max(dp_i21, dp_i10 - price) # 第二次操作之后持股  买入\n",
    "            dp_i10 = max(dp_i10, dp_i11 + price) # 第一次买入之后卖出\n",
    "            dp_i11 = max(dp_i11, -price) # 第一次买入\n",
    "        \n",
    "        return dp_i20\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        if n <= 1: return 0\n",
    "        dp = [[0] * 3 for _ in range(n)]\n",
    "        for j in range(1, 3):\n",
    "            minCost = prices[0]\n",
    "            for i in range(1, n):\n",
    "                minCost = min(minCost, prices[i] - dp[i-1][j-1])\n",
    "                dp[i][j] = max(dp[i-1][j], prices[i] - minCost)\n",
    "        return dp[n-1][2]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        if not prices:\n",
    "            return 0\n",
    "        # 0 没买 1买了1次 2买了1次卖掉， 3买第二次 ， 4卖掉第二次\n",
    "        N = len(prices)\n",
    "        dp = [ [0,0,0,0,0] for _ in range(N) ]\n",
    "        dp[0][1] = - prices[0]\n",
    "        dp[0][3] = - prices[0]\n",
    "        for i in range(1, N):\n",
    "            dp[i][1] = max(dp[i-1][0] - prices[i], dp[i-1][1])\n",
    "            dp[i][2] = max(dp[i-1][1] + prices[i], dp[i-1][2])\n",
    "            dp[i][3] = max(dp[i-1][3], dp[i-1][2] - prices[i])\n",
    "            dp[i][4] = max(dp[i-1][4], dp[i-1][3] + prices[i])\n",
    "        #print(dp)\n",
    "        return max(dp[N-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        if len(prices) == 0:\n",
    "            return 0\n",
    "        f = [[float(\"-inf\"),float(\"-inf\"),float(\"-inf\"),float(\"-inf\")] for _ in range(len(prices))]\n",
    "        f[0][0] = -prices[0]\n",
    "        for i in range(1,len(prices)):\n",
    "            f[i][0] = max(f[i-1][0],-prices[i])\n",
    "            f[i][1] = max(f[i-1][1], f[i-1][0] + prices[i])\n",
    "            f[i][2] = max(f[i-1][2], f[i-1][1]-prices[i])\n",
    "            f[i][3] = max(f[i-1][3], f[i-1][2]+prices[i])\n",
    "        # print(f)\n",
    "        return max(max(f[-1]),0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n =len(prices)\n",
    "        if n < 2:\n",
    "            return 0\n",
    "        dp = [ [[0, 0, 0], [0, 0, 0]]  for _ in range(n)] # dp[a][b][c] a为天数，b取（0，1）分别为未持有和持有股票，c为交易完成次数\n",
    "\n",
    "        dp[0][0][0] = 0 \n",
    "        dp[0][0][1] = float('-inf')\n",
    "        dp[0][0][2] = float('-inf')\n",
    "        dp[0][1][0] = -prices[0]\n",
    "        dp[0][1][1] = float('-inf')\n",
    "        dp[0][1][2] = float('-inf')\n",
    "\n",
    "        for i in range(1, n):\n",
    "            dp[i][0][0] = 0 \n",
    "            dp[i][0][1] = max(dp[i-1][0][1], dp[i-1][1][0]+prices[i])\n",
    "            dp[i][0][2] = max(dp[i-1][0][2], dp[i-1][1][1]+prices[i])\n",
    "            dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][0][0]-prices[i])\n",
    "            dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][1]-prices[i])\n",
    "            dp[i][1][2] = float('-inf')\n",
    "        return max(dp[-1][0][1], dp[-1][0][2], 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        buy1 = buy2 = -prices[0]\n",
    "        sell1 = sell2 = 0\n",
    "        for i in range(1, len(prices)):\n",
    "            buy1 = max(buy1, -prices[i])\n",
    "            sell1 = max(sell1, buy1 + prices[i])\n",
    "            buy2 = max(buy2, sell1 - prices[i])\n",
    "            sell2 = max(sell2, buy2 + prices[i])\n",
    "        return sell2\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n=len(prices)\n",
    "        buy1=buy2=-prices[0]\n",
    "        sell1=sell2=0\n",
    "        for i in range(1,n):\n",
    "            buy1=max(buy1,-prices[i])\n",
    "            sell1=max(sell1,buy1+prices[i])\n",
    "            buy2=max(buy2,sell1-prices[i])\n",
    "            sell2=max(sell2,buy2+prices[i])\n",
    "        return sell2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        buy1 = buy2 = -prices[0]\n",
    "        sell1 = sell2 = 0\n",
    "        for i in range(1, n):\n",
    "            buy1 = max(buy1, -prices[i])\n",
    "            sell1 = max(sell1, buy1 + prices[i])\n",
    "            buy2 = max(buy2, sell1 - prices[i])\n",
    "            sell2 = max(sell2, buy2 + prices[i])\n",
    "        return sell2\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def maxProfit(self, prices: List[int]) -> int:\n",
    "#         n = len(prices)\n",
    "#         dp = [[0,0,0,0] for _ in range(n)]\n",
    "#         dp[0]=[-prices[0],0,-prices[0],0]\n",
    "#         for i in range(1,n):\n",
    "#             dp[i][0] = max(dp[i-1][0], -prices[i])\n",
    "#             dp[i][1] = max(dp[i-1][1], + prices[i] + dp[i-1][0])\n",
    "#             dp[i][2] = max(dp[i-1][2], - prices[i] + dp[i-1][1])\n",
    "#             dp[i][3] = max(dp[i-1][3], + prices[i] + dp[i-1][2])\n",
    "#         return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        f1, f2, f3, f4 = -prices[0],0,-prices[0],0\n",
    "        for price in prices[1:]:\n",
    "            f1 = max(f1,-price)\n",
    "            f2 = max(f2,f1+price)\n",
    "            f3 = max(f3,f2-price)\n",
    "            f4 = max(f4,f3+price)\n",
    "        return f4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        left = [0] * n\n",
    "        mn = prices[0]\n",
    "        right = [0] * n\n",
    "        mx = prices[-1]\n",
    "        for i in range(1, n):\n",
    "            mn = min(mn, prices[i])\n",
    "            left[i] = max(left[i - 1], prices[i] - mn)\n",
    "            ii = n - 1 - i\n",
    "            mx = max(mx, prices[ii])\n",
    "            right[ii] = max(right[ii + 1], mx - prices[ii])\n",
    "        ans = right[0]\n",
    "        for i in range(n - 1):\n",
    "            ans = max(ans, left[i] + right[i + 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        size = len(prices)\n",
    "        if size <= 1:\n",
    "            return 0\n",
    "        b1 = [0] * size\n",
    "        s1 = [0] * size\n",
    "        b2 = [0] * size\n",
    "        s2 = [0] * size\n",
    "\n",
    "        b1[0] = -1 * prices[0]\n",
    "        b2[0] = -1 * prices[0]\n",
    "\n",
    "        for i in range(1, size):\n",
    "            b1[i] = max(b1[i-1], -1 * prices[i])\n",
    "            s1[i] = max(s1[i-1], b1[i-1] + prices[i])\n",
    "            b2[i] = max(b2[i-1], s1[i-1] - prices[i])\n",
    "            s2[i] = max(s2[i-1], b2[i-1] + prices[i])\n",
    "\n",
    "        return s2[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        #1544\n",
    "        n=len(prices)\n",
    "        \n",
    "        dp1=[0]*n\n",
    "        dp2=[0]*n\n",
    "        \n",
    "        dp3=[0]*n\n",
    "        dp4=[0]*n\n",
    "        dp1[0]=-prices[0]\n",
    "        dp2[0]=-inf\n",
    "        dp3[0]=-inf\n",
    "        dp4[0]=-inf\n",
    "        for i in range(1,n):\n",
    "            dp1[i]=max(dp1[i-1],-prices[i])\n",
    "            dp2[i]=max(dp2[i-1],dp1[i-1]+prices[i])\n",
    "            dp3[i]=max(dp3[i-1],dp2[i-1]-prices[i])\n",
    "            dp4[i]=max(dp4[i-1],dp3[i-1]+prices[i])\n",
    "        print(dp1)\n",
    "        print(dp2)\n",
    "        print(dp3)\n",
    "        print(dp4)\n",
    "        return max(dp4[-1],dp2[-1],0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        if len(prices) < 2:\n",
    "            return 0\n",
    "\n",
    "        dp = [[0,0,0,0,0] for _ in range(len(prices))]\n",
    "        a = 0\n",
    "        b = -prices[0]\n",
    "        c = -float('inf')\n",
    "        d = -float('inf')\n",
    "        e = -float('inf')\n",
    "\n",
    "        for i in range(1, len(prices)):\n",
    "            bb = max(b, a-prices[i])\n",
    "            cc = max(c, b+prices[i])\n",
    "            dd = max(d, c-prices[i])\n",
    "            ee = max(e, d+prices[i])\n",
    "            b = bb \n",
    "            c = cc \n",
    "            d = dd \n",
    "            e = ee\n",
    "        return max(a,b,c,d,e)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        ''' \n",
    "                  1  2  3  4  5 \n",
    "        1st hold -1 -1 -1 -1 -1\n",
    "        1st sell  0  1  2  3  4 \n",
    "        2nd hold -1 -1 -1 -1 -1 \n",
    "        2nd sell  0  1  2  3  4\n",
    "        ''' \n",
    "        dp = [[0] * len(prices) for _ in range(4)] \n",
    "\n",
    "        dp[0][0] = -prices[0] \n",
    "        dp[2][0] = -prices[0]   \n",
    "        dp[1][0] = 0 \n",
    "        dp[3][0] = 0 \n",
    "\n",
    "        for i in range(1, len(prices)): \n",
    "            dp[0][i] = max(dp[0][i-1], -prices[i]) \n",
    "            dp[1][i] = max(dp[1][i-1], dp[0][i] + prices[i]) \n",
    "            dp[2][i] = max(dp[2][i-1], dp[1][i] - prices[i]) \n",
    "            dp[3][i] = max(dp[3][i-1], dp[2][i] + prices[i]) \n",
    "        \n",
    "        print(dp)\n",
    "        return dp[-1][-1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def maxProfit(self, prices: List[int]) -> int:\n",
    "#         fb, fs, sb, ss = float('inf'), 0, float('inf'), 0\n",
    "#         for price in prices:\n",
    "#             fb = min(fb, price)  \n",
    "#             fs = max(fs, price-fb)  \n",
    "#             sb = min(sb, price-fs) \n",
    "#             ss = max(ss, price-sb)  \n",
    "#         return ss\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        dp = [[0,0,0,0] for _ in range(n)]\n",
    "        dp[0]=[-prices[0],0,-prices[0],0]\n",
    "        for i in range(1,n):\n",
    "            dp[i][0] = max(dp[i-1][0], -prices[i])\n",
    "            dp[i][1] = max(dp[i-1][1], + prices[i] + dp[i-1][0])\n",
    "            dp[i][2] = max(dp[i-1][2], - prices[i] + dp[i-1][1])\n",
    "            dp[i][3] = max(dp[i-1][3], + prices[i] + dp[i-1][2])\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        # dp[i][1]第一次持有 = max（dp[i-1][1],-prices[i]）\n",
    "        # dp[i][2]第一次不持有 = max(dp[i-1][2],dp[i-1][1]+prices[i])\n",
    "        # dp[i][3]第二次持有 = max(dp[i-1][3],dp[i-1][2]-prices[i])\n",
    "        # dp[i][4]第二次不持有 = max(dp[i-1][4],dp[i-1][3] +prices[i])\n",
    "        n = len(prices)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        dp = [[0]*5 for _ in range(n)]\n",
    "        dp[0][1],dp[0][3], = -prices[0],-prices[0]\n",
    "        dp[0][0] = 0\n",
    "        for i in range(1,n):\n",
    "            dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i])\n",
    "            dp[i][2] = max(dp[i-1][2],dp[i-1][1] +prices[i])\n",
    "            dp[i][3] = max(dp[i-1][3],dp[i-1][2] -prices[i])\n",
    "            dp[i][4] = max(dp[i-1][4],dp[i-1][3]+prices[i])\n",
    "        return dp[-1][4]\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        dp = [[0] * 5 for _ in range(len(prices))]\n",
    "        dp[0] = [0, -prices[0], 0, -prices[0], 0]\n",
    "        for i, price in enumerate(prices[1:], 1):\n",
    "            for j in range(1, 5):\n",
    "                dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + ((-1) ** j) * prices[i])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        dp = [[0 for _ in range(5)] for _ in range(len(prices))]\n",
    "        dp[0][0], dp[0][1], dp[0][2], dp[0][3], dp[0][4] = 0, -prices[0], 0, -prices[0], 0\n",
    "        for i in range(1, len(prices)):\n",
    "            dp[i][1] = max(dp[i-1][1], - prices[i])\n",
    "            dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i])\n",
    "            dp[i][3] = max(dp[i-1][3], dp[i-1][2] - prices[i])\n",
    "            dp[i][4] = max(dp[i-1][4], dp[i-1][3] + prices[i])\n",
    "        return dp[-1][4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        dp=[]\n",
    "        for i in range(len(prices)):\n",
    "           dp.append([0,0])\n",
    "        dp[0][1]=-prices[0]\n",
    "        dp1=[]\n",
    "        for i in range(len(prices)):\n",
    "           dp1.append([0,0])\n",
    "        dp1[0][1]=-prices[0]\n",
    "        for i in range(1,len(dp)):\n",
    "            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])\n",
    "            dp[i][1]=max(dp[i-1][1],-prices[i])\n",
    "            dp1[i][0]=max(dp1[i-1][0],dp1[i-1][1]+prices[i])\n",
    "            dp1[i][1]=max(dp1[i-1][1],dp[i-1][0]-prices[i])\n",
    "        return dp1[-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        numslen = len(prices)\n",
    "        if numslen == 0 :\n",
    "            return 0 \n",
    "            \n",
    "        dp = [[0 for i in range(5)] for j in range(numslen)]#新建二维数组\n",
    "\n",
    "        dp[0][1] = -prices[0];\n",
    "        dp[0][3] = -prices[0];\n",
    "\n",
    "        for i in range(1, numslen):\n",
    "            dp[i][0] = dp[i - 1][0];\n",
    "            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);\n",
    "            dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);\n",
    "            dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);\n",
    "            dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);\n",
    "\n",
    "        print(dp)\n",
    "\n",
    "        return dp[numslen - 1][4] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "\"\"\"\n",
    "状态表示\n",
    "第几天 x 交易了几次 x [未买入、买入、持有、卖出]\n",
    "\n",
    "i天，第一次交易，未买入 = i-1天，第一次交易，未买入\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        dp = np.zeros((n, 2, 4), dtype='int')\n",
    "\n",
    "        for i in range(n):\n",
    "            dp[i] = -1e11\n",
    "            if i == 0:\n",
    "                dp[0][0][0] = 0\n",
    "                dp[0][0][1] = -prices[0]\n",
    "            else:\n",
    "                dp[i][0][0] = dp[i-1][0][0]\n",
    "                dp[i][0][1] = dp[i-1][0][0] - prices[i]\n",
    "                dp[i][0][2] = max(dp[i-1][0][1], dp[i-1][0][2])\n",
    "                dp[i][0][3] = max(dp[i-1][0][1], dp[i-1][0][2]) + prices[i]\n",
    "\n",
    "                dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][0][3])\n",
    "                dp[i][1][1] = max(dp[i-1][1][0], dp[i-1][0][3]) - prices[i]\n",
    "                dp[i][1][2] = max(dp[i-1][1][1], dp[i-1][1][2])\n",
    "                dp[i][1][3] = max(dp[i-1][1][1], dp[i-1][1][2]) + prices[i]\n",
    "\n",
    "        return int(np.max(dp))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "\"\"\"\n",
    "状态表示\n",
    "第几天 x 交易了几次 x [未买入、买入、持有、卖出]\n",
    "\n",
    "i天，第一次交易，未买入 = i-1天，第一次交易，未买入\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        dp = np.zeros((n, 2, 4), dtype='int')\n",
    "\n",
    "        v = 0\n",
    "        for i in range(n):\n",
    "            dp[i] = -1e11\n",
    "            if i == 0:\n",
    "                dp[0][0][0] = 0\n",
    "                dp[0][0][1] = -prices[0]\n",
    "            else:\n",
    "                dp[i][0][0] = dp[i-1][0][0]\n",
    "                dp[i][0][1] = dp[i-1][0][0] - prices[i]\n",
    "                dp[i][0][2] = max(dp[i-1][0][1], dp[i-1][0][2])\n",
    "                dp[i][0][3] = max(dp[i-1][0][1], dp[i-1][0][2]) + prices[i]\n",
    "\n",
    "                dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][0][3])\n",
    "                dp[i][1][1] = max(dp[i-1][1][0], dp[i-1][0][3]) - prices[i]\n",
    "                dp[i][1][2] = max(dp[i-1][1][1], dp[i-1][1][2])\n",
    "                dp[i][1][3] = max(dp[i-1][1][1], dp[i-1][1][2]) + prices[i]\n",
    "\n",
    "            v = max(v, np.max(dp[i]))\n",
    "        return int(v)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "\n",
    "        K = 2\n",
    "        # 前i天经过k次买/卖后，手头最大收益\n",
    "        bought = [[float(\"-inf\") for k in range(K + 1)] for i in range(len(prices) + 1)]\n",
    "        sold = [[0 for k in range(K + 1)] for i in range(len(prices) + 1)]\n",
    "\n",
    "        for i in range(1, len(prices) + 1):\n",
    "            for k in range(1, K + 1):\n",
    "                # 第i天经过k次买卖\n",
    "                bought[i][k] = max(\n",
    "                    # 前一天经过k-1次完整买卖，手头不持有，今天买入\n",
    "                    sold[i - 1][k - 1] - prices[i - 1],\n",
    "                    # 前一天，经k次买入，手头持有\n",
    "                    bought[i - 1][k],\n",
    "                )\n",
    "                # 第i天，k次买入\n",
    "                sold[i][k] = max(\n",
    "                    # 前一天，经k次买入，手头持有，今天卖出\n",
    "                    bought[i - 1][k] + prices[i - 1],\n",
    "                    # 前一天，经k次完整买卖，手头不持有\n",
    "                    sold[i - 1][k],\n",
    "                )\n",
    "        \n",
    "        return sold[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        l=len(prices)\n",
    "        # 0：持0  1：持1\n",
    "        # 0：不持0 1： 不持1 2：不持2  \n",
    "        dp=[[[0,0],[0,0,0]] for i in range(l)]\n",
    "        dp[0]=[[-prices[0],-prices[0]],[0,0,0]]\n",
    "        for i in range(1,l):\n",
    "            # 持0  不持0买 持0 \n",
    "            dp[i][0][0]=max(dp[i-1][1][0]-prices[i],dp[i-1][0][0])\n",
    "            # 持1 不持1买 持1 持0卖买\n",
    "            dp[i][0][1]=max(dp[i-1][1][1]-prices[i],dp[i-1][0][1])\n",
    "            # 不持0 不持0\n",
    "            dp[i][1][0]=dp[i-1][1][0]\n",
    "            # 不持1 不持1 持0卖\n",
    "            dp[i][1][1]=max(dp[i-1][1][1],dp[i-1][0][0]+prices[i])\n",
    "            # 不持2 不持2 持1卖\n",
    "            dp[i][1][2]=max(dp[i-1][1][2],dp[i-1][0][1]+prices[i])\n",
    "\n",
    "        return max(dp[l-1][1][1], dp[l-1][1][2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        #dp = [[[0] * 2] * 2] * len(prices)\n",
    "        dp = [[[0] * 2 for _ in range(2)] for _ in range(len(prices))]\n",
    "\n",
    "        \n",
    "        \n",
    "        for i in range(len(prices)):\n",
    "            if i == 0:\n",
    "                dp[0][0][1] = -prices[0]\n",
    "                dp[0][1][1] = -prices[0]\n",
    "            else:\n",
    "                dp[i][0][0] = max(dp[i - 1][0][0], dp[i - 1][0][1] + prices[i])\n",
    "                dp[i][0][1] = max(dp[i - 1][0][1], 0 - prices[i])\n",
    "                dp[i][1][0] = max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])\n",
    "                dp[i][1][1] = max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i])\n",
    "\n",
    "        \n",
    "        return dp[-1][1][0]\n",
    "                 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices) -> int:\n",
    "        n = len(prices)\n",
    "        dp = [[[0] * 3 for _ in range(2)] for _ in range(n)]\n",
    "        dp[0][0][0] = 0\n",
    "        dp[0][0][1] = 0\n",
    "        dp[0][0][2] = 0\n",
    "        dp[0][1][0] = -prices[0]\n",
    "        dp[0][1][1] = -prices[0]\n",
    "        dp[0][1][2] = -9999999\n",
    "        for i in range(1, n):\n",
    "                dp[i][0][2] = 0\n",
    "                dp[i][1][2] = -9999999\n",
    "        for i in range(1, n):\n",
    "            k = 1\n",
    "            while k >= 0:\n",
    "                dp[i][0][k] = max(dp[i-1][1][k] + prices[i], dp[i-1][0][k])\n",
    "                dp[i][1][k] = max(dp[i-1][0][k+1] - prices[i], dp[i-1][1][k])\n",
    "                k -= 1\n",
    "        return max(dp[n-1][0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        #复制\n",
    "        n=len(prices)\n",
    "        dp=[[[0,0,0],[0,0,0]] for _ in range(n)]\n",
    "        dp[0][1][0]=-prices[0]\n",
    "        dp[0][0][1]=-inf\n",
    "        dp[0][0][2]=-inf\n",
    "        dp[0][1][1]=-inf\n",
    "        dp[0][1][2]=-inf\n",
    "        for i in range(1,n):\n",
    "            #未持股，未卖出过，说明从未进行过买卖\n",
    "            dp[i][0][0]=0\n",
    "            #未持股，卖出过1次，可能是今天卖的，可能是之前卖的\n",
    "            dp[i][0][1]=max(dp[i-1][1][0]+prices[i],dp[i-1][0][1])\n",
    "            #未持股，卖出过2次，可能是今天卖的，可能是之前卖的\n",
    "            dp[i][0][2]=max(dp[i-1][1][1]+prices[i],dp[i-1][0][2])\n",
    "            #持股，未卖出过，可能是今天买的，可能是之前买的\n",
    "            dp[i][1][0]=max(dp[i-1][0][0]-prices[i],dp[i-1][1][0])\n",
    "            #持股，卖出过1次，可能是今天买的，可能是之前买的\n",
    "            dp[i][1][1]=max(dp[i-1][0][1]-prices[i],dp[i-1][1][1])\n",
    "            #持股，卖出过2次，不可能\n",
    "            dp[i][1][2]=-inf\n",
    "        return max(dp[n-1][0][1],dp[n-1][0][2],0)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#垃圾\n",
    "    # def maxProfit(self, prices: List[int]) -> int:\n",
    "    #     low1=high1=prices[0]\n",
    "    #     low2=high2=prices[len(prices)-1]\n",
    "    #     profit1=[0]*len(prices)\n",
    "    #     profit2=[0]*len(prices)\n",
    "    #     profit=profit3=profit4=0\n",
    "    #     for i in range(0,len(prices)):\n",
    "    #         if(prices[i]<low1):\n",
    "    #             high1=low1=prices[i]\n",
    "    #         if(prices[i]>high1):\n",
    "    #             high1=prices[i]\n",
    "    #         profit3=max(profit3,high1-low1)\n",
    "    #         profit1[i]=profit3\n",
    "    #         if(prices[len(prices)-1-i]<low2):\n",
    "    #             low2=prices[len(prices)-1-i]\n",
    "    #         if(prices[len(prices)-1-i]>high2):\n",
    "    #             high2=low2=prices[len(prices)-1-i]\n",
    "    #         profit4=max(profit4,high2-low2)\n",
    "    #         profit2[len(prices)-1-i]=profit4\n",
    "    #     for k in range(0,len(prices)):\n",
    "    #         profit = max(profit,profit1[k]+profit2[k])\n",
    "    #         print(profit)\n",
    "    #     return profit\n",
    "    # def maxProfit(self, prices: List[int]) -> int:\n",
    "    #     n = len(prices)\n",
    "    #     buy1 = buy2 = -prices[0]\n",
    "    #     sell1 = sell2 = 0\n",
    "    #     for i in range(1, n):\n",
    "    #         buy1 = max(buy1, -prices[i])\n",
    "    #         sell1 = max(sell1, buy1 + prices[i])\n",
    "    #         buy2 = max(buy2, sell1 - prices[i])\n",
    "    #         sell2 = max(sell2, buy2 + prices[i])\n",
    "    #     return sell2\n",
    "\n",
    "\n",
    "\n",
    "       #超时！！！\n",
    "        # n = len(prices)\n",
    "        # profit = max(prices[-1] - prices[0], 0)\n",
    "        # for j in range(1, n):  # 调整循环范围\n",
    "        #     # 第一次交易的最大利润\n",
    "        #     profit1 = 0\n",
    "        #     min_price1 = prices[0]\n",
    "        #     for i in range(j):\n",
    "        #         min_price1 = min(min_price1, prices[i])\n",
    "        #         profit1 = max(profit1, prices[i] - min_price1)\n",
    "\n",
    "        #     # 第二次交易的最大利润\n",
    "        #     profit2 = 0\n",
    "        #     max_price2 = prices[-1]\n",
    "        #     for i in range(n - 1, j - 1, -1):  # 调整循环范围\n",
    "        #         max_price2 = max(max_price2, prices[i])\n",
    "        #         profit2 = max(profit2, max_price2 - prices[i])\n",
    "\n",
    "        #     # 总的最大利润\n",
    "        #     profit = max(profit, profit1 + profit2)\n",
    "\n",
    "        # return profit\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        # dp[天][是否持有][已经完成几次]\n",
    "        if len(prices) == 0:\n",
    "            return 0\n",
    "        dp = [[[0, 0, 0] for _ in range(2)] for _ in range(len(prices) + 1)]\n",
    "        dp[0][0][1] = -inf\n",
    "        dp[0][0][2] = -inf\n",
    "        dp[0][1][0] = -prices[0]\n",
    "        dp[0][1][1] = -inf\n",
    "        dp[0][1][2] = -inf\n",
    "        for i in range(1, len(prices) + 1):\n",
    "            dp[i][0][0] = 0\n",
    "            dp[i][0][1] = max(dp[i-1][0][1], dp[i-1][1][0] + prices[i-1])\n",
    "            dp[i][0][2] = max(dp[i-1][0][2], dp[i-1][1][1] + prices[i-1])\n",
    "            dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][0][0] - prices[i-1])\n",
    "            dp[i][1][1] = max(dp[i-1][1][1],  dp[i-1][0][1] - prices[i-1])\n",
    "            dp[i][1][2] = -inf\n",
    "        return max(dp[i][0][2], dp[i][0][1], 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        if not prices:\n",
    "            return 0\n",
    "\n",
    "        n = len(prices)\n",
    "        max_trade = 2\n",
    "        dp = [[[0]*2 for _ in range(max_trade+1)] for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(max_trade, 0, -1):\n",
    "                if i == 0:\n",
    "                    dp[i][j][0] = 0\n",
    "                    dp[i][j][1] = -prices[i]\n",
    "                else:\n",
    "                    dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])\n",
    "                    dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])\n",
    "\n",
    "        return dp[n-1][max_trade][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        # @cache\n",
    "        # def dfs(i,hold,k):\n",
    "        #     if k < 0:\n",
    "        #         return -inf\n",
    "        #     if i < 0:\n",
    "        #         return 0 if not hold else -inf\n",
    "        #     if hold:\n",
    "        #         return max(dfs(i-1,True,k),dfs(i-1,False,k)-prices[i])\n",
    "        #     return max(dfs(i-1,False,k),dfs(i-1,True,k-1)+prices[i])\n",
    "        # return dfs(n-1,False,2)\n",
    "        f = [[[-inf] * 4 for _ in range(2)] for _ in range(n+1)]\n",
    "        for i in range(1,4):\n",
    "            f[0][0][i] = 0\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,4):\n",
    "                f[i][0][j] = max(f[i-1][0][j],f[i-1][1][j-1]+prices[i-1])\n",
    "                f[i][1][j] = max(f[i-1][1][j],f[i-1][0][j]-prices[i-1])\n",
    "\n",
    "        return f[n][0][3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        k = 2\n",
    "        n = len(prices)\n",
    "        ans = [[[-float('inf')]*2 for _ in range(k + 1)] for _ in range(n + 1)]\n",
    "        for j in range(k+1):\n",
    "            ans[0][j][0] = 0\n",
    "        for i in range(1, n + 1):\n",
    "            ans[i][0] = ans[i-1][0]\n",
    "            for j in range(1, k + 1):\n",
    "                ans[i][j][0] = max(ans[i-1][j][1] + prices[i-1], ans[i-1][j][0])\n",
    "                ans[i][j][1] = max(ans[i-1][j-1][0] - prices[i-1], ans[i-1][j][1])\n",
    "        return ans[n][k][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        N = len(prices)\n",
    "        # 状态定义 dp[i][j][k]代表在第i天，被允许完成j次交易时，持有或者不持有的最大利润。k=0代表不持有，k=1代表持有\n",
    "        dp = [[[0 for k in range(2)] for j in range(3)] for i in range(N)]\n",
    "\n",
    "        for i in range(N):\n",
    "            for j in range(1, 3):\n",
    "                # badcase\n",
    "                if i - 1 == -1:\n",
    "                    dp[i][j][0] = 0\n",
    "                    dp[i][j][1] = -prices[i]\n",
    "                else:\n",
    "                    dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])\n",
    "                    dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])\n",
    "\n",
    "        return dp[N-1][2][0]\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        max_k = 2\n",
    "        dp = [[[0] * 2 for _ in range(max_k + 2)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for k in range(max_k, 0, -1):\n",
    "                if i - 1 == -1:\n",
    "                    dp[i][k][0] = 0\n",
    "                    dp[i][k][1] = -prices[i]\n",
    "                    continue\n",
    "                dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])\n",
    "                dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])\n",
    "        return dp[n-1][max_k][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        买卖股票所获得的最大的利润\n",
    "        Args:\n",
    "            prices (list[int]): 每天的股票价格\n",
    "        returns (int): 最终所能够获得的最大利润\n",
    "        \"\"\"\n",
    "        #处理异常情况\n",
    "        if prices == None or len(prices) <= 1:\n",
    "            return 0 \n",
    "        \n",
    "        n = len(prices)\n",
    "        \n",
    "        #dp的定义, dp[i][j][k]表示[...i]天的情况下, 在拥有股票(1表示拥有股票, 0表示不拥有股票), 已经发生k次交易的情况下, 所能够获得的最大的利润\n",
    "        dp = [[[-float('inf') for _ in range(3)] for _ in range(2)] for _ in range(n)]\n",
    "\n",
    "        #dp的初始化\n",
    "        dp[0][0][0] = 0             #在第0天不进行操作\n",
    "        dp[0][1][0] = -prices[0]    #在第0天买入股票\n",
    "        \n",
    "        #dp的遍历, dp的状态转移\n",
    "        for i in range(1, n):\n",
    "            #1.第i天持有股票\n",
    "                #case1.1 未进行过交易(卖出操作), 可能的情况为(前一天拥有股票且未进行过交易; 前一天不拥有股票且没有进行过交易, 今天买入股票)\n",
    "            dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][0][0] - prices[i])\n",
    "                \n",
    "                #case1.2 进行了一次交易, 可能存在的情况为(前一天拥有股票且进行过一次交易今天不操作； 前一天不拥有股票且进行过一次交易， 今天买入股票)\n",
    "            dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][1] - prices[i])\n",
    "                \n",
    "                #case1.3 进行了两次交易, 此种方法必然不是最大值\n",
    "            dp[i][1][2] = -float(\"inf\")\n",
    "            \n",
    "            #2.第i天不持有股票\n",
    "                #case2.1 没有进行过交易\n",
    "            dp[i][0][0] = dp[i-1][0][0] \n",
    "                \n",
    "                #case2.2 进行过一次交易\n",
    "            dp[i][0][1] = max(dp[i-1][0][1], dp[i-1][1][0] + prices[i])\n",
    "                \n",
    "                #case2.3 进行过两次交易\n",
    "            dp[i][0][2] = max(dp[i-1][0][2], dp[i-1][1][1] + prices[i])\n",
    "        \n",
    "        ans = 0\n",
    "        #遍历dp, 找寻最大利润\n",
    "        for i in range(n):\n",
    "            for j in range(2):\n",
    "                for k in range(3):\n",
    "                    if dp[i][j][k] > ans:\n",
    "                        ans = dp[i][j][k]\n",
    "        \n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        import numpy as np\n",
    "        dp = [[[-1e10 for _ in range(3)] for _ in range(2)] for _ in range(len(prices))]\n",
    "        dp[0][0][0] = 0\n",
    "        dp[0][1][0] = -prices[0]\n",
    "        for i in range(1, len(prices)):\n",
    "            dp[i][0][0] = dp[i-1][0][0]\n",
    "            dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][0][0] - prices[i])\n",
    "            dp[i][0][1] = max(dp[i-1][0][1], dp[i-1][1][0] + prices[i])\n",
    "            dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][1] - prices[i])\n",
    "            dp[i][0][2] = max(dp[i-1][0][2], dp[i-1][1][1] + prices[i])\n",
    "        return max(dp[-1][0][0], dp[-1][0][1], dp[-1][0][2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        dp = [[[0] * 2 for _ in range(4)] for _ in range(n + 1)]\n",
    "        for i in range(n + 1):\n",
    "            for j in range(4):\n",
    "                for k in range(2):\n",
    "                    if i == 0:\n",
    "                        dp[i][j][k] = -inf if k == 1 else 0\n",
    "                    elif j == 0:\n",
    "                        dp[i][j][k] = -inf\n",
    "                    else:\n",
    "                        if k:\n",
    "                            dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j][0] - prices[i - 1])\n",
    "                        else:\n",
    "                            dp[i][j][0] = max(dp[i - 1][j - 1][1] + prices[i - 1], dp[i - 1][j][0])\n",
    "        return dp[n][3][0]\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        \n",
    "        # 动态规划\n",
    "        # dp = [[[-inf] * ]]\n",
    "        # 递归\n",
    "        # @cache\n",
    "        # def dfs(i, j, hold):\n",
    "        #     if j < 0:\n",
    "        #         return -inf\n",
    "        #     if i < 0:\n",
    "        #         return -inf if hold else 0\n",
    "        #     if hold:\n",
    "        #         return max(dfs(i - 1, j, True), dfs(i - 1, j, False) - prices[i])\n",
    "        #     return max(dfs(i - 1, j, False), dfs(i - 1, j - 1, True) + prices[i])\n",
    "        # return dfs(len(prices) - 1, 2, False)\n",
    "\n",
    "        # 二刷 2023 11 21\n",
    "        # 法一 递归\n",
    "        # @cache\n",
    "        # def dfs(i, j, hold):\n",
    "        #     if j < 0:\n",
    "        #         return -inf\n",
    "        #     if i < 0:\n",
    "        #         return -inf if hold else 0\n",
    "        #     if hold:\n",
    "        #         return max(dfs(i-1, j, True), dfs(i-1, j-1, False) - prices[i])\n",
    "        #     return max(dfs(i-1, j, False), dfs(i-1, j, True) + prices[i])\n",
    "        # return dfs(len(prices) - 1, 2, False)\n",
    "\n",
    "        # 法二 动态规划\n",
    "        n = len(prices)\n",
    "        dp = [[[-inf] * 2 for _ in range(4)] for _ in range(n+1)]\n",
    "        for j in range(1, 4):\n",
    "            dp[0][j][0] = 0\n",
    "        for i, p in enumerate(prices):\n",
    "            for j in range(1, 4):\n",
    "                dp[i+1][j][0] = max(dp[i][j][0], dp[i][j][1] + p)\n",
    "                dp[i+1][j][1] = max(dp[i][j][1], dp[i][j-1][0] - p)\n",
    "        return dp[n][3][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        dp = np.zeros((len(prices), 3, 2), dtype = int).tolist()\n",
    "        for i in range(3):\n",
    "            dp[0][i][1] = -prices[0]\n",
    "        for i in range(1, len(prices)):\n",
    "            dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][2][1]+prices[i])\n",
    "            dp[i][2][1] = max(dp[i-1][2][1], dp[i-1][1][0]-prices[i])\n",
    "            dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1]+prices[i])\n",
    "            dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0]-prices[i])\n",
    "        return dp[len(prices)-1][2][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        k=2\n",
    "        n=len(prices)\n",
    "        dp=[[[-float(\"inf\") for _ in range(2)]for _ in range(k+1)]for _ in range(n)]\n",
    "        for i in range(k+1):\n",
    "            dp[0][i][0]=0\n",
    "            dp[0][i][1]=-prices[0]\n",
    "        for i in range(1,n):\n",
    "            for j in range(k+1):\n",
    "                if j==0:\n",
    "                    dp[i][j][0]=0\n",
    "                if j!=0:\n",
    "                    dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j-1][1]+prices[i])\n",
    "                dp[i][j][1]=max(dp[i-1][j][1],dp[i][j][0]-prices[i])\n",
    "        #print(dp)\n",
    "        return dp[-1][-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        import numpy\n",
    "        if not prices:\n",
    "            return 0\n",
    "        duration = len(prices)\n",
    "    # 结束时的最高利润=[天数][是否持有股票][卖出次数]\n",
    "        profit = [[[0, 0, 0], [0, 0, 0]] for i in range(0, duration)]\n",
    "    # 第一天休息\n",
    "        profit[0][0][0] = 0\n",
    "    # 第一天买入\n",
    "        profit[0][1][0] = -prices[0]\n",
    "    # 第一天不可能已经有卖出\n",
    "        profit[0][0][1] = float('-inf')\n",
    "        profit[0][0][2] = float('-inf')\n",
    "    # 第一天不可能已经卖出\n",
    "        profit[0][1][1] = float('-inf')\n",
    "        profit[0][1][2] = float('-inf')\n",
    "        for i in range(1, duration):\n",
    "        # 未持股，未卖出过，说明从未进行过买卖\n",
    "            profit[i][0][0] = 0\n",
    "        # 未持股，卖出过1次，可能是今天卖的，可能是之前卖的\n",
    "            profit[i][0][1] = max(profit[i - 1][1][0] + prices[i], profit[i - 1][0][1])\n",
    "        # 未持股，卖出过2次，可能是今天卖的，可能是之前卖的\n",
    "            profit[i][0][2] = max(profit[i - 1][1][1] + prices[i], profit[i - 1][0][2])\n",
    "        # 持股，未卖出过，可能是今天买的，可能是之前买的\n",
    "            profit[i][1][0] = max(profit[i - 1][0][0] - prices[i], profit[i - 1][1][0])\n",
    "        # 持股，卖出过1次，可能是今天买的，可能是之前买的\n",
    "            profit[i][1][1] = max(profit[i - 1][0][1] - prices[i], profit[i - 1][1][1])\n",
    "        # 持股，卖出过2次，不可能\n",
    "            profit[i][1][2] = float('-inf')\n",
    "        return max(profit[duration - 1][0][1], profit[duration - 1][0][2], 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        import numpy as np\n",
    "\n",
    "        #init\n",
    "        dp = [[[0 for i in range(2)] for j in range(3)] for k in range(len(prices))]\n",
    "        for i in range(3):\n",
    "            for j in range(2):\n",
    "                dp[0][i][j] = -np.inf\n",
    "        dp[0][0][0] = 0\n",
    "        dp[0][0][1] = - prices[0]\n",
    "\n",
    "\n",
    "        #transition functionm\n",
    "        for i in range(1,len(prices)):\n",
    "            for j in range(3):\n",
    "                dp[i][j][1] = max(dp[i - 1][j][1], dp[i-1][j][0] - prices[i])\n",
    "                if j>=1:\n",
    "                    dp[i][j][0] = max(dp[i - 1][j][0], dp[i-1][j - 1][1] + prices[i])\n",
    "                else:\n",
    "                    dp[i][j][0] = 0\n",
    "\n",
    "        res = 0\n",
    "        for i in range(3):\n",
    "            if dp[-1][i][0]>res:\n",
    "                res = dp[-1][i][0]\n",
    "        print(res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        # prices = [7,6,4,3,1] \n",
    "        n = len(prices)\n",
    "        K = 2*2\n",
    "        dp = [[[0] * 2 for _ in range(K + 1)] for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            dp[i][0][0] = 0\n",
    "            dp[i][0][1] = -float('inf')\n",
    "            for j in range(K, 0, -1):\n",
    "                if i-1 == -1:\n",
    "                    dp[i][j][0] = 0\n",
    "                    dp[i][j][1] = -prices[i]\n",
    "                    continue\n",
    "\n",
    "                # 1.昨天未持有，今天rest 2.昨天持有，今天卖了\n",
    "                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j-1][1] + prices[i])\n",
    "\n",
    "                # 1.昨天持有，今天rest 2.昨天未持有，今天买了\n",
    "                dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])\n",
    "                \n",
    "        return dp[n-1][K][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        dp = [ [ [ 0 for i in range(2) ] for j in range(5) ] for k in range(len(prices)+5) ]\n",
    "        INF = 1e9+7\n",
    "        dp[0][0][1] = -prices[0]\n",
    "        dp[0][0][0] = 0\n",
    "        dp[0][1][1] = -INF\n",
    "        dp[0][1][0] = -INF\n",
    "        dp[0][2][1] = -INF\n",
    "        dp[0][2][0] = -INF\n",
    "        ans = -1\n",
    "        for i in range(1, len(prices)):\n",
    "            dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][1][1] + prices[i])\n",
    "            dp[i][2][1] = max(dp[i-1][2][1], dp[i-1][2][0] - prices[i])\n",
    "\n",
    "            dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][0][1]+prices[i])\n",
    "            dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][1][0] - prices[i])\n",
    "            dp[i][0][0] = dp[i-1][0][0]\n",
    "            dp[i][0][1] = max( dp[i-1][0][1], dp[i-1][0][0] - prices[i] )\n",
    "\n",
    "        ans = max(ans, dp[len(prices)-1][2][0])\n",
    "        ans = max(ans, dp[len(prices)-1][1][0])\n",
    "        ans = max(ans, dp[len(prices)-1][0][0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        k = 2\n",
    "\n",
    "        f = [[[-inf, -inf] for _ in range(k + 2)] for _ in range(n + 1)]\n",
    "\n",
    "        for j in range(1, k + 2):\n",
    "            f[0][j][0] = 0\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, k + 2):\n",
    "                f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j][0] - prices[i - 1])\n",
    "                f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j - 1][1] + prices[i - 1])\n",
    "\n",
    "        return f[n][k + 1][0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "    \n",
    "    ## 定义dp[i][k][0]表示第i天且进行了k（k=0，1，2）次交易（不持有股票）的最大收益\n",
    "    ## 定义dp[i][k][1]表示第i天且进行了k次交易（持有股票）的最大收益\n",
    "    ## dp[i][k][1] = max(dp[i-1][k][0]-prices[i],dp[i-1][k-1][1])\n",
    "    ## dp[i][k][0] = max(dp[i-1][k][0],dp[i-1][k-1][1]+prices[i])\n",
    "    ## 初始条件： dp[i][k][0] = 0 dp[i][k][1] = -prices[0] k= 0 1 2\n",
    "\n",
    "        length = len(prices)\n",
    "        if length<2:\n",
    "            return 0\n",
    "        dp = np.zeros([length,3,2]).tolist()\n",
    "\n",
    "        for k in range(3):\n",
    "            dp[0][k][0] = 0\n",
    "            dp[0][k][1] = -prices[0]\n",
    "\n",
    "        for i in range(1,length):\n",
    "            dp[i][0][0] = 0\n",
    "            dp[i][0][1] = max(dp[i-1][0][1],dp[i-1][0][0]-prices[i])\n",
    "            for k in range(1,3):\n",
    "                dp[i][k][0] = max(dp[i-1][k][0],dp[i-1][k-1][1]+prices[i])\n",
    "                dp[i][k][1] = max(dp[i-1][k][1],dp[i-1][k][0]-prices[i])\n",
    "\n",
    "        return dp[length-1][2][0]\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sys import maxsize\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        profit[day][k][hold_stock]\n",
    "        0 <= day <= len(prices)-1\n",
    "        k: the max number of transaction so far. 0 <= k <= 2\n",
    "        hold_stock: 0 False, 1 True\n",
    "        \"\"\"\n",
    "        days = len(prices)\n",
    "        K = 2\n",
    "        profit = [[[-maxsize-1 for _ in range(2)] for _ in range(K+1)] for _ in range(days)]\n",
    "\n",
    "        # base cases day = 0\n",
    "        for k in range(K+1):\n",
    "            profit[0][k][0] = 0\n",
    "            profit[0][k][1] = -prices[0]\n",
    "        # base cases k = 0\n",
    "        for day in range(days):\n",
    "            profit[day][0][0] = 0\n",
    "\n",
    "        for day in range(1, days):\n",
    "            for k in range(1, K+1):\n",
    "                profit[day][k][0] = max(profit[day-1][k][0], profit[day-1][k][1] + prices[day])\n",
    "                profit[day][k][1] = max(profit[day-1][k][1], profit[day-1][k-1][0] - prices[day])\n",
    "        return profit[days-1][K][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "\n",
    "        vals = [[[-math.inf for x in range(2)] for y in range(3)] for z in range(len(prices))]\n",
    "\n",
    "        vals[0][2][0] = 0\n",
    "        vals[0][1][1] = -prices[0]\n",
    "\n",
    "        for i in range(1, len(prices)):\n",
    "\n",
    "            vals[i][2][0] = vals[i-1][2][0]\n",
    "\n",
    "            for j in range(2):\n",
    "                vals[i][j][0] = max(vals[i-1][j][1] + prices[i], vals[i-1][j][0]) # if no stock today, either sell or stay same\n",
    "                vals[i][j][1] = max(vals[i-1][j+1][0] - prices[i], vals[i-1][j][1]) # if have stock today, either buy or stay same\n",
    "            \n",
    "        print(vals[len(prices)-1])\n",
    "        print([vals[len(prices)-1][i][0] for i in range(2)])\n",
    " \n",
    "        return max([vals[len(prices)-1][i][0] for i in range(3)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        # 记忆化搜索\n",
    "        # @lru_cache(None)\n",
    "        # def dfs(day, j, hold):\n",
    "        #     if j < 0:\n",
    "        #          return -inf\n",
    "        #     if day == -1:\n",
    "        #         return -inf if hold else 0\n",
    "        #     if hold:\n",
    "        #         return max(dfs(day-1, j, True), dfs(day-1, j-1, False)-prices[day])\n",
    "        #     else:\n",
    "        #         return max(dfs(day-1, j, False), dfs(day-1, j, True)+prices[day])\n",
    "        # n = len(prices)\n",
    "        # return dfs(n-1, 2, False)\n",
    "        # 递推\n",
    "        k = 2\n",
    "        n = len(prices)\n",
    "        dp = [[[-inf for _ in range(2)] for _ in range(k+2)] for _ in range(n+1)]\n",
    "        for i in range(k+2):\n",
    "            dp[0][i][0] = 0\n",
    "            dp[0][i][1] = -inf\n",
    "        for i in range(n):\n",
    "            for j in range(1, k+2):\n",
    "                dp[i+1][j][0] = max(dp[i][j][0], dp[i][j-1][1]+prices[i])\n",
    "                dp[i+1][j][1] = max(dp[i][j][1], dp[i][j][0]-prices[i])\n",
    "        return dp[n][k+1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        index = {(i,j):0 for i in range(n) for j in range(4)}\n",
    "        index[0,0] = -prices[0]\n",
    "        index[0,2] = -prices[0]\n",
    "        for i in range(1, n):\n",
    "            index[i,0] = max(index[i-1,0], - prices[i])\n",
    "            index[i,1] = max(index[i-1,1], index[i-1, 0] + prices[i])\n",
    "            index[i,2] = max(index[i-1,2], index[i-1, 1] - prices[i])\n",
    "            index[i,3] = max(index[i-1,3], index[i-1, 2] + prices[i])\n",
    "        return index[n-1,3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        dp = {}\n",
    "        dp[('no', 0, 0)] = float('-inf')\n",
    "        dp[('no', 0, 1)] = float('-inf')\n",
    "        dp[('no', 0, 2)] = 0\n",
    "        dp[('yes', 0, 1)] = -prices[0]\n",
    "        dp[('yes', 0, 0)] = float('-inf')\n",
    "\n",
    "        for i in range(1, len(prices)):\n",
    "            dp[('yes', i, 1)] = max(dp[('yes', i - 1, 1)], dp[('no', i - 1, 2)] - prices[i])\n",
    "            dp[('yes', i, 0)] = max(dp[('yes', i - 1, 0)], dp[('no', i - 1, 1)] - prices[i])\n",
    "\n",
    "            dp[('no', i, 2)] = dp[('no', i - 1, 2)]\n",
    "            dp[('no', i, 1)] = max(dp[('no', i - 1, 1)], dp[('yes', i - 1, 1)] + prices[i])\n",
    "            dp[('no', i, 0)] = max(dp[('no', i - 1, 0)], dp[('yes', i - 1, 0)] + prices[i])\n",
    "        \n",
    "        return max(max(dp[('no', len(prices) - 1, 0)], dp[('no', len(prices) - 1, 1)]), dp[('no', len(prices) - 1, 2)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        a = self.f2(prices)\n",
    "        self.f1(prices)\n",
    "        return a\n",
    "\n",
    "    def f2(self, prices):\n",
    "        dp = [[[0 for _ in range(2)] for _ in range(3)] for _ in range(len(prices)+1)]\n",
    "        dp[0][0][1] = -inf\n",
    "        dp[0][1][1] = -inf\n",
    "        dp[0][2][1] = -inf\n",
    "        for i in range(1, len(prices)+1):\n",
    "            for j in range(1, 3):\n",
    "                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i-1])\n",
    "                dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i-1])\n",
    "        import numpy as np\n",
    "        print(np.array(dp))\n",
    "        return dp[-1][-1][0]\n",
    "\n",
    "    def f1(self, prices):\n",
    "        l=len(prices)\n",
    "        import numpy as np\n",
    "        dp=np.zeros([l+1,3,2])\n",
    "        dp[0,:,1]=-np.inf\n",
    "        for i in range(1,l+1):\n",
    "            for j in range(1,3):\n",
    "                dp[i,j,0] = max(dp[i-1,j,0],dp[i-1,j,1]+prices[i-1])\n",
    "                dp[i,j,1] = max(dp[i-1,j,1],dp[i-1,j-1,0]-prices[i-1])\n",
    "        print(dp)\n",
    "        return int(dp[-1,-1,0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        dic = {}\n",
    "        dic[(0,0)] = 0\n",
    "        dic[(0,1)] = -prices[0]\n",
    "        dic[(0,2)] = 0\n",
    "        dic[(0,3)] = -prices[0]\n",
    "        dic[(0,4)] = 0\n",
    "        max_val = 0\n",
    "        for i in range(1, len(prices)):\n",
    "            cur_p = prices[i]\n",
    "            dic[(i,0)] = 0\n",
    "            dic[(i,1)] = max(dic[(i-1,1)], -cur_p)\n",
    "            dic[(i,2)] = max(cur_p+dic[(i-1,1)], dic[(i-1,2)])\n",
    "            max_val = max(max_val, dic[(i,2)])\n",
    "            dic[(i,3)] = max(dic[(i-1,2)]-cur_p, dic[(i-1,3)])\n",
    "            dic[(i,4)] = max(dic[(i-1,4)],cur_p + dic[(i-1,3)])\n",
    "            max_val = max(max_val, dic[(i,4)])\n",
    "        return max_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        dp = {}\n",
    "        dp[(0,0,0)] = 0 # I天买入k次当前不持有 利润\n",
    "        dp[(0,1,1)] = -prices[0]\n",
    "        dp[(0,1,0)] = 0\n",
    "        dp[(0,2,1)] = -prices[0]\n",
    "        dp[(0,2,0)] = 0\n",
    "        for i in range(1, len(prices)):\n",
    "            dp[(i,0,0)] = dp[(i-1,0,0)]\n",
    "            dp[(i,1,0)] = max(dp[(i-1,1,0)], dp[(i-1,1,1)] + prices[i])\n",
    "            dp[(i,2,0)] = max(dp[(i-1,2,0)], dp[(i-1,2,1)] + prices[i])\n",
    "\n",
    "            dp[(i,1,1)] = max(dp[(i-1,1,1)], dp[(i-1,0,0)] - prices[i])\n",
    "            dp[(i,2,1)] = max(dp[(i-1,2,1)], dp[(i-1,1,0)]-prices[i], dp[(i-1,1,1)])\n",
    "        return max(0, dp[(len(prices)-1,0,0)], dp[(len(prices)-1,1,0)], dp[(len(prices)-1,2,0)], dp[(len(prices)-1,1,1)], dp[(len(prices)-1,2,1)] ) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "\n",
    "        n = len(prices)\n",
    "        k = 2\n",
    "        k = min(k, n//2)\n",
    "        ans = 0\n",
    "        dp = defaultdict(lambda: float('-inf'))\n",
    "        \n",
    "        # iteration \n",
    "        dp[(0, 0, \"buy\")] = -prices[0]\n",
    "        for i in range(1, n):\n",
    "            dp[(i, 0, \"buy\")] = max(dp[(i-1, 0, \"buy\")], -prices[i])\n",
    "\n",
    "        # bound \n",
    "        for i in range(1, len(prices)):\n",
    "            for j in range(1, k+1):    \n",
    "                dp[(i, j, \"sell\")] = max(dp[(i-1, j-1,  \"buy\")] + prices[i], dp[(i-1, j, \"sell\")])    \n",
    "                dp[(i, j,  \"buy\")] = max(dp[(i-1,   j, \"sell\")] - prices[i], dp[(i-1, j, \"buy\")])    \n",
    "                ans = max(ans, dp[(i, j, \"sell\")])\n",
    "                 \n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        dp = {}\n",
    "        max_k = 2\n",
    "        for i in range(len(prices)):\n",
    "            dp[i] = {}\n",
    "            for k in range (max_k, 0, -1):\n",
    "                dp[i][k] = {}\n",
    "                if i - 1 == -1:\n",
    "                    dp[i][k][0] = 0\n",
    "                    dp[i][k][1] = -prices[i]\n",
    "                    continue\n",
    "                \n",
    "                dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])\n",
    "                \n",
    "                if k - 1 == 0:\n",
    "                    dp[i][k][1] = max(dp[i - 1][k][1],  - prices[i])\n",
    "                else:\n",
    "                    dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])\n",
    "        \n",
    "        return dp[len(prices) - 1][max_k][0]\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        dp = [[[-inf for k in range(2)] for j in range(2+1)] for i in range(n+1)]\n",
    "        #[i,j,k]->i表示第几天，j表示至多交易了几次(0次，1次，2次)，k表示是否含股票(0不含，1含)\n",
    "        dp = np.array(dp)\n",
    "        #print(np.array(dp).shape)   #(9,3,2)\n",
    "        #初始化 \n",
    "        for i in range(n+1):   \n",
    "            dp[i][0][0] = 0\n",
    "            dp[i][0][1] = -inf\n",
    "        for j in range(2+1):\n",
    "            dp[0][j][0] = 0\n",
    "            dp[0][j][1] = -prices[0]\n",
    "        #循环-把买入当成一次交易\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1,3):\n",
    "                #不含且最多交易了j次  =max(昨天不含且交易了j次-不操作，昨天含且交易了j次-卖出)\n",
    "                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]+prices[i-1])\n",
    "                #  含且最多交易了j次  =max(昨天含且交易了j次-不操作，昨天不含且交易了j-1-买入)\n",
    "                dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0]-prices[i-1])\n",
    "        # print(dp)\n",
    "\n",
    "        return int(max(dp[-1][-1][0], dp[-1][-1][1]))\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        trades = 2\n",
    "        dp = [[{'cash': 0, 'stock': -float('inf')} for kth_trade in range(trades + 1)] for day in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            for k in range(1, trades + 1):\n",
    "                dp[i][k]['cash'] = max(dp[i - 1][k]['cash'], dp[i - 1][k]['stock'] + prices[i - 1])\n",
    "                dp[i][k]['stock'] = max(dp[i - 1][k]['stock'], dp[i - 1][k - 1]['cash'] - prices[i - 1])\n",
    "        return max([dp[-1][k]['cash'] for k in range(1, trades + 1)])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        count = 2\n",
    "        dp = dict()\n",
    "        for i in range(n):\n",
    "            dp[(i,0,0)] = 0\n",
    "            dp[(i,1,0)] = float(\"-inf\")\n",
    "        for k in range(1, count+1):\n",
    "            dp[(0,0,k)] = 0\n",
    "            dp[(0,1,k)] = -prices[0]\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            for k in range(1, count+1):\n",
    "                dp[(i,0,k)] = max(dp.get((i-1,0,k), 0), dp.get((i-1,1,k),0)+prices[i])\n",
    "                dp[(i,1,k)] = max(dp.get((i-1,1,k), 0), dp.get((i-1,0,k-1),0)-prices[i])\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for k in range(count+1):\n",
    "                res = max(res, dp.get((i,0,k), 0))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        # 状态与选择\n",
    "        # 状态：赚到的钱\n",
    "        # 选择：时间，交易次数，是否持有\n",
    "        dp = {}\n",
    "\n",
    "        # 遍历某个变量，考虑另一个变量为极端值的情况\n",
    "        for i in range(-1, len(prices)):\n",
    "            dp[(i, 0, 0)] = 0\n",
    "            dp[(i, 0, 1)] = -sys.maxsize\n",
    "        \n",
    "        for k in range(3):\n",
    "            dp[(-1, k, 0)] = 0\n",
    "            dp[(-1, k, 1)] = -sys.maxsize\n",
    "\n",
    "        \n",
    "        for i in range(len(prices)):\n",
    "            for k in [1, 2]:\n",
    "                dp[(i, k, 0)] = max(dp[(i-1, k, 0)], dp[(i-1, k, 1)]+prices[i])\n",
    "                dp[(i, k, 1)] = max(dp[(i-1, k, 1)], dp[(i-1, k-1, 0)]-prices[i])\n",
    "\n",
    "        return dp[(len(prices)-1, 2, 0)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        if not prices:\n",
    "            return 0\n",
    "        length = len(prices)\n",
    "\n",
    "        def dfs(depth: int, count: int, is_has_stock: bool):\n",
    "            if depth == length or count == 2:\n",
    "                return 0\n",
    "            profit_sell, profit_buy, profit_nothing = 0, 0, 0\n",
    "            profit_nothing = dfs(depth+1, count, is_has_stock)\n",
    "            if is_has_stock:\n",
    "                profit_sell = dfs(depth+1, count+1, False) + prices[depth]\n",
    "            else:\n",
    "                profit_buy = dfs(depth+1, count, True) - prices[depth]\n",
    "            return max(profit_sell, profit_buy, profit_nothing)\n",
    "        return dfs(0, 0, False)\n",
    "\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        if not prices:\n",
    "            return 0\n",
    "        length = len(prices)\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(depth: int, count: int, is_has_stock: bool):\n",
    "            if depth == length or count == 2:\n",
    "                return 0\n",
    "            profit_sell, profit_buy, profit_nothing = 0, 0, 0\n",
    "            profit_nothing = dfs(depth+1, count, is_has_stock)\n",
    "            if is_has_stock:\n",
    "                profit_sell = dfs(depth+1, count+1, False) + prices[depth]\n",
    "            else:\n",
    "                profit_buy = dfs(depth+1, count, True) - prices[depth]\n",
    "            return max(profit_sell, profit_buy, profit_nothing)\n",
    "        return dfs(0, 0, False)\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        days = len(prices)\n",
    "        if days < 1:\n",
    "            return 0\n",
    "        from collections import defaultdict\n",
    "        dp = defaultdict(lambda :defaultdict(lambda: defaultdict(int)))\n",
    "        dp[0]['buy']['first'] = -prices[0]\n",
    "        dp[0]['buy']['second'] = -prices[0]\n",
    "        for day in range(1, days):\n",
    "            # first buy\n",
    "            dp[day]['buy']['first'] = max(dp[day-1]['buy']['first'], -prices[day])\n",
    "            # first sell\n",
    "            dp[day]['sell']['first'] = max(dp[day-1]['sell']['first'], dp[day-1]['buy']['first']+prices[day])\n",
    "            # second buy\n",
    "            dp[day]['buy']['second'] = max(dp[day-1]['buy']['second'], dp[day-1]['sell']['first']-prices[day])\n",
    "            # second sell\n",
    "            dp[day]['sell']['second'] = max(dp[day-1]['sell']['second'], dp[day-1]['buy']['second']+prices[day])\n",
    "\n",
    "        return  max(max(day_info['sell'].values()) for day_info in dp.values())\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        days = len(prices)\n",
    "        if days < 1:\n",
    "            return 0\n",
    "        from collections import defaultdict\n",
    "        dp = defaultdict(lambda :defaultdict(lambda: defaultdict(int)))\n",
    "        dp[0]['buy']['first'] = -prices[0]\n",
    "        dp[0]['buy']['second'] = -prices[0]\n",
    "        res = 0\n",
    "        for day in range(1, days):\n",
    "            # first buy\n",
    "            dp[day]['buy']['first'] = max(dp[day-1]['buy']['first'], -prices[day])\n",
    "            # first sell\n",
    "            dp[day]['sell']['first'] = max(dp[day-1]['sell']['first'], dp[day-1]['buy']['first']+prices[day])\n",
    "            # second buy\n",
    "            dp[day]['buy']['second'] = max(dp[day-1]['buy']['second'], dp[day-1]['sell']['first']-prices[day])\n",
    "            # second sell\n",
    "            dp[day]['sell']['second'] = max(dp[day-1]['sell']['second'], dp[day-1]['buy']['second']+prices[day])\n",
    "            res = max(res, *dp[day]['sell'].values())\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.prices: Optional[List[int]] = None\n",
    "        self.dp = None\n",
    "\n",
    "    def GetRes(self, ownPrice, times, day) -> int:\n",
    "        if day >= len(self.prices):\n",
    "            return 0\n",
    "        if times >= 2:\n",
    "            return 0\n",
    "\n",
    "        if self.dp[ownPrice][times][day] != -1:\n",
    "            return self.dp[ownPrice][times][day]\n",
    "\n",
    "        if ownPrice == 1:\n",
    "            lhs = self.GetRes(ownPrice, times, day + 1)\n",
    "            rhs = self.GetRes(0, times + 1, day + 1) + self.prices[day]\n",
    "        else:\n",
    "            lhs = self.GetRes(ownPrice, times, day + 1)\n",
    "            rhs = self.GetRes(1, times, day + 1) - self.prices[day]\n",
    "\n",
    "        self.dp[ownPrice][times][day] = max(lhs, rhs)\n",
    "        return self.dp[ownPrice][times][day]\n",
    "\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        self.prices = prices\n",
    "        self.dp = [[[-1 for k in range(len(self.prices))] for j in range(2)] for i in range(2)]\n",
    "        return self.GetRes(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        dp = [[-1 for _ in range(4)] for _ in range(len(prices))]\n",
    "        def dfs(idx, stat):\n",
    "            if idx == len(prices) or stat == 4: return 0\n",
    "            if dp[idx][stat] != -1: return dp[idx][stat]\n",
    "            if stat & 1 == 0:\n",
    "                dp[idx][stat] = max(dfs(idx + 1, stat), dfs(idx + 1, stat + 1) - prices[idx])\n",
    "            else:\n",
    "                dp[idx][stat] = max(dfs(idx + 1, stat), dfs(idx + 1, stat + 1) + prices[idx])\n",
    "            return dp[idx][stat]\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        # dp[n][k][0] = max(dp[n-1][k][0], dp[n-1][k][1] + price)\n",
    "        # dp[n][k][1] = max(dp[n-1][k][1], dp[n-1][k-1][0] - price)\n",
    "        dp = {}\n",
    "        maxK = 2\n",
    "        \n",
    "        for index, price in enumerate(prices):\n",
    "            dp[index] = {}\n",
    "\n",
    "            for k in range(maxK + 1):\n",
    "                dp[index][k] = {}\n",
    "\n",
    "                if index == 0:\n",
    "                    dp[index][k][0] = 0\n",
    "                    dp[index][k][1] = -price\n",
    "                    continue\n",
    "\n",
    "                if k == 0:\n",
    "                    dp[index][k][0] = 0\n",
    "                    dp[index][k][1] = -price\n",
    "                    continue\n",
    "\n",
    "                dp[index][k][0] = max(dp[index-1][k][0], dp[index-1][k][1] + price)\n",
    "                dp[index][k][1] = max(dp[index-1][k][1], dp[index-1][k-1][0] - price)\n",
    "        \n",
    "        return dp[len(prices) - 1][2][0]\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "                 \n",
    "                \n",
    "                \n",
    "                \n",
    "                \n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        dp = [[-1] * 4 for _ in range(len(prices))]\n",
    "        \n",
    "        def dfs(idx, s):\n",
    "            if idx == len(prices) or s == 4:\n",
    "                return 0\n",
    "            if dp[idx][s] != -1:\n",
    "                return dp[idx][s]\n",
    "            if s == 0 or s == 2:\n",
    "                dp[idx][s] = max(dfs(idx + 1, s), dfs(idx + 1, s + 1) - prices[idx])\n",
    "            else:\n",
    "                dp[idx][s] = max(dfs(idx + 1, s), dfs(idx + 1, s + 1) + prices[idx])\n",
    "            return dp[idx][s]\n",
    "        \n",
    "        return dfs(0, 0)\n",
    "        # dp = {}\n",
    "        # @lru_cache(maxsize=None)\n",
    "        # def dfs(index, state):\n",
    "        #     # state 有0买，1卖，2第二次买，3第三次卖，4停\n",
    "        #     if index >= len(prices) or state == 4: return 0\n",
    "        #     if state in [0, 2]:\n",
    "        #         dp[(index, state)] = max(dfs(index+1, state), dfs(index+1, state+1)-prices[index])\n",
    "        #     if state in [1, 3]:\n",
    "        #         dp[(index, state)] = max(dfs(index+1, state), dfs(index+1, state+1)+prices[index])\n",
    "        #     return dp[(index, state)]\n",
    "        # return dfs(0,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "\n",
    "        # dp = [[-prices[0],0] for _ in range(k+1)]\n",
    "\n",
    "        # for j in range(len(prices)):\n",
    "        #     for i in range(1,k+1):\n",
    "        #         dp[i][0] = max(dp[i][0], dp[i-1][1]-prices[j])\n",
    "        #         dp[i][1] = max(dp[i][1], dp[i-1][0]+prices[j])\n",
    "        # return max([dp[i][1] for i in range(len(dp))])\n",
    "\n",
    "        def greedy(prices):\n",
    "            res = 0\n",
    "            for i in range(1, len(prices)):\n",
    "                if prices[i] > prices[i-1]:\n",
    "                    res += prices[i] - prices[i-1]\n",
    "                    \n",
    "            return res\n",
    "\n",
    "        n = len(prices)\n",
    "        if k >= n//2:\n",
    "            return greedy(prices)\n",
    "\n",
    "        buy, sell = [-prices[0]]*k , [0]*(k+1)\n",
    "        for p in prices[0:]:\n",
    "            for i in range(k):\n",
    "                buy[i] = max(buy[i], sell[i-1]-p)\n",
    "                sell[i] = max(sell[i], buy[i]+p)\n",
    "                \n",
    "        return max(sell)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k, prices):\n",
    "        \"\"\"\n",
    "        :type k: int\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(prices)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        \n",
    "        # MLE, 2D DP, O(nk) time/space\n",
    "\n",
    "#         buy = [[0 for i in range(n)] for j in range(k + 1)]\n",
    "#         sell = [[0 for i in range(n)] for j in range(k + 1)]\n",
    "#         for kk in range(k + 1):\n",
    "#             buy[kk][0] = -prices[0]\n",
    "#         for kk in range(1, k + 1):\n",
    "#             sell[kk][0] = 0\n",
    "#         for kk in range(0, k + 1):\n",
    "#             for nn in range(1, n):\n",
    "#                 buy[kk][nn] = max(buy[kk][nn - 1], sell[kk][nn - 1] - prices[nn])\n",
    "#                 if kk:\n",
    "#                     sell[kk][nn] = max(sell[kk][nn - 1], buy[kk - 1][nn - 1] + prices[nn])\n",
    "\n",
    "#         return sell[-1][-1]\n",
    "        \n",
    "        if k >= n / 2:\n",
    "            return sum(i - j for i, j in zip(prices[1:], prices[:-1]) if i - j > 0)\n",
    "        buy_c = [0] * n\n",
    "        sell = [0] * n\n",
    "        buy_c[0] = -prices[0]\n",
    "        for nn in range(1, n):\n",
    "            buy_c[nn] = max(buy_c[nn - 1], sell[nn - 1] - prices[nn])\n",
    "        for kk in range(1, k + 1):\n",
    "            buy_p = buy_c\n",
    "            buy_c = [0] * n\n",
    "            buy_c[0] = -prices[0]\n",
    "            for nn in range(1, n):\n",
    "                buy_c[nn] = max(buy_c[nn - 1], sell[nn - 1] - prices[nn])\n",
    "                sell[nn] = max(sell[nn - 1], buy_p[nn - 1] + prices[nn])\n",
    "\n",
    "        return sell[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit_as_many_transactions(self, prices):\n",
    "        if prices == []:\n",
    "            return 0\n",
    "        profit, prev = 0, prices[0]\n",
    "        for i in range(1, len(prices)):\n",
    "            if prices[i] >= prices[i - 1]:\n",
    "                profit = profit + prices[i] - prices[i - 1]\n",
    "        return profit\n",
    "\n",
    "    def maxProfit(self, K, prices):\n",
    "        \"\"\"\n",
    "        :type k: int\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        reference: # https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/discuss/54135/Python-solution-with-detailed-explanation\n",
    "        we use 2D array dp[k][i] denotes max profile up to prices[i] at most k transactions.For acquiring dp[k][i],we have to consider prices[i].\n",
    "        If we include it,dp[k][i]=[max(dp[k-1][j]+prices[i]-prices[j]) for j in range(0,i-1)],otherwise,dp[k][i]=dp[k][i-1].\n",
    "        Therefore,dp[k][i]=max(dp[k][i-1],max[prices[i]+max(dp[k-1][j]-prices[j]) for j in range(0,i-1)])\n",
    "        dp[k][0]=0\n",
    "        dp[0][i]=0\n",
    "        \"\"\"\n",
    "        if not prices:\n",
    "            return 0\n",
    "        K = min(K, len(prices) - 1)\n",
    "        if K == 0:\n",
    "            return 0\n",
    "        if K >= len(prices) // 2:\n",
    "            return self.maxProfit_as_many_transactions(prices)\n",
    "        N = len(prices)\n",
    "        dp = [[0] * N for _ in range(K + 1)]\n",
    "        for k in range(1, K + 1):\n",
    "            tmpMax = - prices[0]\n",
    "            for i in range(1, N):\n",
    "                dp[k][i] = max(dp[k][i - 1], prices[i] + tmpMax)\n",
    "                # f[k, i] = max(f[k, i-1], price[i] + max(f[k-1, j-1]--price[j]))\n",
    "                # max(f[k-1, j-1]--price[j]) => tmpMax\n",
    "                tmpMax = max(tmpMax, dp[k - 1][i - 1] - prices[i])\n",
    "        return dp[K][N - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#买卖股票的最佳时机 IV  动态规划\n",
    "class Solution(object):\n",
    "    def maxProfit(self, k, prices):\n",
    "        \"\"\"\n",
    "        :type k: int\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def greedy(prices):\n",
    "            max_ = 0\n",
    "            for i in range(1, len(prices)):\n",
    "                max_ += max(0, prices[i]-prices[i-1])\n",
    "            return max_\n",
    "        if k >= len(prices)//2:\n",
    "            return greedy(prices)\n",
    "        dp = [[0 for i in range(len(prices))] for j in range(k+1)]\n",
    "        for x in range(1, k+1):\n",
    "            mx = dp[x-1][0] - prices[0]\n",
    "            for i in range(1, len(prices)):\n",
    "                dp[x][i] = max(dp[x][i-1], prices[i] + mx)\n",
    "                mx = max(mx, dp[x-1][i]-prices[i])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k, prices):\n",
    "        \"\"\"\n",
    "        :type k: int\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(prices) <= 1: return 0\n",
    "        if k == 0: return 0\n",
    "        if k > len(prices):return self.greddy(prices)\n",
    "        helper = [[[0 for i in range(len(prices))] for i in range(k + 1)] for i in range(2)]\n",
    "        for j in range(0, len(prices), 1):\n",
    "            for h in range(0, k + 1, 1):\n",
    "                if j == 0:\n",
    "                    helper[0][h][j] = 0\n",
    "                    helper[1][h][j] = -prices[0]\n",
    "                elif h == 0:\n",
    "                    helper[0][h][j] = 0\n",
    "                    helper[1][h][j] = max(-prices[j], helper[1][h][j - 1])\n",
    "                else:\n",
    "                    helper[0][h][j] = max(helper[0][h][j - 1], helper[1][h - 1][j - 1] + prices[j])\n",
    "                    helper[1][h][j] = max(helper[1][h][j - 1], helper[0][h][j - 1] - prices[j])\n",
    "\n",
    "        maxN = 0\n",
    "        for l in range(0, k + 1, 1):\n",
    "            maxN = max(helper[0][l][len(prices) - 1], maxN)\n",
    "        return maxN\n",
    "    def greddy(self,prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        sum = 0\n",
    "        for i, price in enumerate(prices):\n",
    "            if i == len(prices) - 1:\n",
    "                break\n",
    "            if price < prices[i + 1]:\n",
    "                sum += prices[i + 1] - price\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dprogramming(self, k, prices):\n",
    "        \"\"\"\n",
    "        :type k: int\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if k <= 0 or len(prices) == 0:\n",
    "            return 0\n",
    "        l = [[0 for _ in range(k+1)] for _ in range(len(prices))]\n",
    "        g = [[0 for _ in range(k+1)] for _ in range(len(prices))]\n",
    "        for i in range(1,len(prices)):\n",
    "            diff = prices[i] - prices[i-1]\n",
    "            for j in range(1,k+1):\n",
    "                l[i][j] = max(g[i-1][j-1] + max(0, diff), l[i-1][j] + diff)\n",
    "                g[i][j] = max(l[i][j], g[i-1][j])\n",
    "        return g[-1][-1]\n",
    "    \n",
    "    def maxProfit(self, k, prices):\n",
    "        \"\"\"\n",
    "        :type k: int\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(prices) < 2:\n",
    "            return 0\n",
    "        # 按照递增序列分段\n",
    "        sums = []\n",
    "        # 跟踪上一个递增序列的最小值\n",
    "        lasti = 0\n",
    "        for i in range(1, len(prices)):\n",
    "            if prices[i] < prices[i-1]:\n",
    "                if prices[i-1] - prices[lasti] > 0:\n",
    "                    sums.append((prices[lasti], prices[i-1]))\n",
    "                # 将递增序列的前端点置为当前节点\n",
    "                lasti = i\n",
    "        # 如果递增直至最后一个元素，需要额外处理\n",
    "        if prices[-1] - prices[lasti] > 0:\n",
    "            sums.append((prices[lasti], prices[-1]))\n",
    "        # print(\"sums\", sums)\n",
    "        # k次交易的profit一定大于k-1次，所以，\n",
    "        # 只需要求k次的即可\n",
    "        if k >= len(sums):\n",
    "            return sum([i[1]-i[0] for i in sums])\n",
    "        else:\n",
    "            np = []\n",
    "            for a, b in sums:\n",
    "                np.append(a)\n",
    "                np.append(b)\n",
    "            return self.dprogramming(k, np)\n",
    "        \"\"\"\n",
    "        window = len(sums) - k\n",
    "        ksums = [i for i in sums]\n",
    "        # 依次递减交易量\n",
    "        while window > 0:\n",
    "            # 缩减到k词交易带来的损失\n",
    "            ksums = self.shrink1trade(ksums)\n",
    "            #sums = [i for i in ksums]\n",
    "            #ksums.clear()\n",
    "            window -= 1\n",
    "        return sum([i[1]-i[0] for i in ksums])\n",
    "        \"\"\"\n",
    "\n",
    "    def shrink1trade(self, profits):\n",
    "        \"\"\"减少一笔交易的最大收益\n",
    "        \n",
    "        减少一笔交易包括剔除一笔或者合并相邻两笔（中间不交易）\n",
    "        \"\"\"\n",
    "        # print(\"\\t======\", profits)\n",
    "        ploss = 10**10\n",
    "        pi = 0\n",
    "        for i in range(len(profits)):\n",
    "            if ploss > profits[i][1] - profits[i][0]:\n",
    "                ploss = profits[i][1] - profits[i][0]\n",
    "                pi = i\n",
    "            if i + 1 < len(profits):\n",
    "                mergeloss = profits[i][1] - profits[i+1][0]\n",
    "                if ploss > mergeloss:\n",
    "                    ploss = mergeloss\n",
    "                    pi = i\n",
    "        np = []\n",
    "        i = 0\n",
    "        while i < len(profits):\n",
    "            if pi == i:\n",
    "                if ploss != profits[i][1] - profits[i][0]:\n",
    "                    # 合并\n",
    "                    np.append((profits[i][0], profits[i+1][1]))\n",
    "                    i += 1\n",
    "                else:\n",
    "                    # 删除，不需要处理\n",
    "                    pass\n",
    "            else:\n",
    "                np.append((profits[i][0], profits[i][1]))\n",
    "            i += 1\n",
    "        return np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "    # F[i,k,0] = max F[i-1,k,0] F[i-1,k,1]+a[i]\n",
    "    # F[i,k,1] = max F[i-1,k,1] F[i-1,k+1]-a[i]\n",
    "\n",
    "        \n",
    "        if k == 0 or prices == None or len(prices) == 0:\n",
    "            return 0\n",
    "        if k <= len(prices)//2 :\n",
    "            d = [-9999 for _ in range(2 * k)]\n",
    "            d[2*k-2] = 0\n",
    "            for i, price in enumerate(prices):\n",
    "                nd = []\n",
    "                for ki in range(k):\n",
    "                    empty = d[2*ki]\n",
    "                    inhand = d[2*ki+1]\n",
    "                    nd.append(max(empty, inhand+price))\n",
    "                    nd.append(max(inhand, (d[2*ki+2]-price) if ki!=k-1 else -price))\n",
    "                #print(d)\n",
    "                d = nd\n",
    "            ans = 0\n",
    "            for ki in range(k):\n",
    "                if ans < d[ki*2]:\n",
    "                    ans = d[ki*2]\n",
    "        else:\n",
    "            ans = 0\n",
    "            buy = prices[0]\n",
    "            for price in prices:\n",
    "                if price > buy:\n",
    "                    ans += (price - buy)\n",
    "                buy = price\n",
    "                    \n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        if n == 0: return 0\n",
    "        dp0 = [-prices[0]] * (k+1)\n",
    "        dp1 = [0] * (k+1)\n",
    "        for p in prices[1:]:\n",
    "            for i in range(1, k+1):\n",
    "                dp1[i] = max(dp1[i], dp0[i]+p)\n",
    "                dp0[i] = max(dp0[i], dp1[i-1]-p)\n",
    "        return max(dp1[k], 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        l = len(prices)\n",
    "        if l<=1:\n",
    "            return 0\n",
    "        dp = [[0,-prices[0]] for _ in range(k)] #k次的 0不持有和1持有\n",
    "        for i in range(1,l):\n",
    "            p = prices[i]\n",
    "            for j in range(k):\n",
    "                last_profit = dp[j-1][0] if j !=0 else 0\n",
    "                dp[j][1] = max(dp[j][1],last_profit-p)#找到一个最好的买点 \n",
    "                dp[j][0] = max(dp[j][0],dp[j][1]+p)   #找到一个最好的卖点  之前就卖掉/现在卖掉套现\n",
    "        return dp[-1][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        have = [-sys.maxsize]*k\n",
    "        no_have = [-sys.maxsize]*k\n",
    "        have[0] = -prices[0]\n",
    "        for i in range(len(prices)):\n",
    "            for j in range(k-1,0,-1):\n",
    "                no_have[j] = max(have[j]+prices[i],no_have[j])\n",
    "                have[j] = max(no_have[j-1]-prices[i],have[j])\n",
    "            no_have[0] = max(have[0]+prices[i],no_have[0])\n",
    "            have[0] = max(-prices[i],have[0])\n",
    "        return max(max(no_have),0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        if not prices:\n",
    "            return 0\n",
    "        n = len(prices)\n",
    "        k = min(k, n // 2)\n",
    "        buy = [float('-inf')] * (k + 1)\n",
    "        sell = [float('-inf')] * (k + 1)\n",
    "        buy[0], sell[0] = -prices[0], 0\n",
    "        for i in range(1, n):\n",
    "            buy[0] = max(buy[0], sell[0] - prices[i])\n",
    "            for j in range(1, k + 1):\n",
    "                buy[j] = max(buy[j], sell[j] - prices[i])\n",
    "                sell[j] = max(sell[j], buy[j - 1] + prices[i])\n",
    "        return max(sell)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        if not prices or k == 0:\n",
    "            return 0\n",
    "\n",
    "        n = len(prices)\n",
    "        if k >= n // 2:\n",
    "            # 如果 k 大于等于 n//2，可以进行尽可能多的交易\n",
    "            return sum(max(prices[i + 1] - prices[i], 0) for i in range(n - 1))\n",
    "\n",
    "        # 初始化 dp 数组\n",
    "        dp = [[0] * (k + 1) for _ in range(n)]\n",
    "\n",
    "        # 填充 dp 数组\n",
    "        for j in range(1, k + 1):\n",
    "            max_diff = -prices[0]\n",
    "            for i in range(1, n):\n",
    "                dp[i][j] = max(dp[i - 1][j], prices[i] + max_diff)\n",
    "                max_diff = max(max_diff, dp[i][j - 1] - prices[i])\n",
    "\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        if not prices:\n",
    "            return 0\n",
    "\n",
    "        n = len(prices)\n",
    "        k = min(k, n // 2)\n",
    "        buy = [[0] * (k + 1) for _ in range(n)]\n",
    "        sell = [[0] * (k + 1) for _ in range(n)]\n",
    "\n",
    "        buy[0][0], sell[0][0] = -prices[0], 0\n",
    "        for i in range(1, k + 1):\n",
    "            buy[0][i] = sell[0][i] = float(\"-inf\")\n",
    "\n",
    "        for i in range(1, n):\n",
    "            buy[i][0] = max(buy[i - 1][0], sell[i - 1][0] - prices[i])\n",
    "            for j in range(1, k + 1):\n",
    "                buy[i][j] = max(buy[i - 1][j], sell[i - 1][j] - prices[i])\n",
    "                sell[i][j] = max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]);  \n",
    "\n",
    "        return max(sell[n - 1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        n=len(prices)\n",
    "        dp=[[0]*(2*k) for _ in range(n)]\n",
    "        dp[0][:]=[-prices[0],0]*k\n",
    "        for i in range(1,n):\n",
    "            dp[i][0]=max(dp[i-1][0],0-prices[i])\n",
    "            dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i])\n",
    "            # 第一次特殊处理\n",
    "            for j in range(1,k):\n",
    "                dp[i][2*j]=max(dp[i-1][2*j],dp[i-1][2*j-1]-prices[i])\n",
    "                dp[i][2*j+1]=max(dp[i-1][2*j+1],dp[i-1][2*j]+prices[i])\n",
    "        return dp[n-1][2*k-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "\n",
    "        dp = [[0]* (2*k+1) for _ in range(len(prices))]\n",
    "        for i in range(k):\n",
    "            dp[0][2*i+1] = -prices[0]\n",
    "            \n",
    "        for i in range(1, len(prices)):\n",
    "            for j in range(2*k+1):\n",
    "                if j ==0:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    if j % 2==0:\n",
    "                        dp[i][j] = max(dp[i-1][j-1]+prices[i], dp[i-1][j])\n",
    "                    else:\n",
    "                        dp[i][j] = max(dp[i-1][j-1]-prices[i], dp[i-1][j])\n",
    "        \n",
    "        return dp[len(prices)-1][2*k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices) -> int:\n",
    "        n = len(prices)\n",
    "        dp = [[[0] * (k+1) for _ in range(2)] for _ in range(n)]\n",
    "        dp[0][1][k] = -9999999\n",
    "        for m in range(k):\n",
    "            dp[0][1][m] = -prices[0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "                dp[i][0][k] = 0\n",
    "                dp[i][1][k] = -9999999\n",
    "        for i in range(1, n):\n",
    "            m = k-1\n",
    "            while m >= 0:\n",
    "                dp[i][0][m] = max(dp[i-1][1][m] + prices[i], dp[i-1][0][m])\n",
    "                dp[i][1][m] = max(dp[i-1][0][m+1] - prices[i], dp[i-1][1][m])\n",
    "                m -= 1\n",
    "        return max(dp[n-1][0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        m = len(prices)\n",
    "        dp = [[-1] * m for _ in range(2 * k)]\n",
    "        def dfs(s, index):\n",
    "            if index == len(prices) or s == 2 * k:\n",
    "                return 0\n",
    "            if dp[s][index] != -1:\n",
    "                return dp[s][index]\n",
    "            if s % 2 == 0:\n",
    "                dp[s][index] = max(dfs(s, index + 1), dfs(s + 1, index + 1) - prices[index])\n",
    "            else:\n",
    "                dp[s][index] = max(dfs(s, index + 1), dfs(s + 1, index + 1) + prices[index])\n",
    "            return dp[s][index]\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        dp = [\n",
    "            [float('-inf') for j in range(2*k)]\n",
    "            for i in range(n)\n",
    "        ]\n",
    "\n",
    "        dp[0][0] = -prices[0]\n",
    "        \n",
    "        ans = 0\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            for j in range(2*k):\n",
    "                if j == 0:\n",
    "                    dp[i][j] = max(dp[i-1][j], -prices[i])\n",
    "                else:\n",
    "                    if j % 2 == 1:\n",
    "                        dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + prices[i])\n",
    "                    else:\n",
    "                        dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] - prices[i])\n",
    "\n",
    "                ans = max(ans, dp[i][j])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        dp = [\n",
    "            [float('-inf') for j in range(2*k)]\n",
    "            for i in range(n)\n",
    "        ]\n",
    "\n",
    "        dp[0][0] = -prices[0]\n",
    "        \n",
    "        ans = 0\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            for j in range(2*k):\n",
    "                if j == 0:\n",
    "                    dp[i][j] = max(dp[i-1][j], -prices[i])\n",
    "                else:\n",
    "                    if j % 2 == 1:\n",
    "                        dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + prices[i])\n",
    "                    else:\n",
    "                        dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] - prices[i])\n",
    "\n",
    "                ans = max(ans, dp[i][j])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        # n = len(prices)\n",
    "        # if k>2:\n",
    "        #     sell1=0\n",
    "        #     buy1=-prices[0]\n",
    "        #     sell=[0]*(k-1)\n",
    "        #     buy=[-prices[0]]*(k-1)\n",
    "        #     for i in range(1, n):\n",
    "        #         buy1 = max(buy1, -prices[i])\n",
    "        #         sell1 = max(sell1, buy1 + prices[i])\n",
    "        #         for j in range(k-1):\n",
    "        #             buy[j] = max(buy[j], sell[j] - prices[i])\n",
    "        #             sell[j] = max(sell[j], buy[j] + prices[i])\n",
    "        #     return sell[k-2]\n",
    "        # elif k==2:\n",
    "        #     buy1 = buy2 = -prices[0]\n",
    "        #     sell1 = sell2 = 0\n",
    "        #     for i in range(1, n):\n",
    "        #         buy1 = max(buy1, -prices[i])\n",
    "        #         sell1 = max(sell1, buy1 + prices[i])\n",
    "        #         buy2 = max(buy2, sell1 - prices[i])\n",
    "        #         sell2 = max(sell2, buy2 + prices[i])\n",
    "        #     return sell2\n",
    "        # else:\n",
    "        #     low=high=prices[0]\n",
    "        #     profit=0\n",
    "        #     for i in prices:\n",
    "        #         if(i<low):\n",
    "        #             high=low=i\n",
    "        #         if(i>high):\n",
    "        #             high=i\n",
    "        #         profit=max(profit,high-low)\n",
    "        #     return profit\n",
    "\n",
    "            if not prices or k == 0:\n",
    "                return 0\n",
    "\n",
    "            n = len(prices)\n",
    "\n",
    "            # 如果 k 的值大于 n//2，可以进行无限次交易，直接使用贪心算法解决\n",
    "            if k >= n // 2:\n",
    "                return sum(max(prices[i + 1] - prices[i], 0) for i in range(n - 1))\n",
    "\n",
    "            # 初始化动态规划数组\n",
    "            dp = [[[0] * 2 for _ in range(k + 1)] for _ in range(n)]\n",
    "\n",
    "            # 初始状态\n",
    "            for i in range(k + 1):\n",
    "                dp[0][i][1] = -prices[0]\n",
    "\n",
    "            # 动态规划更新数组\n",
    "            for i in range(1, n):\n",
    "                for j in range(k, 0, -1):\n",
    "                    dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i])\n",
    "                    dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i])\n",
    "\n",
    "            # 返回最大值\n",
    "            return dp[n - 1][k][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        dp = [[[0, 0] for _ in range(k+1)] for __ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][0][1] = -prices[i]\n",
    "            dp[i][0][0] = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(k, 0, -1):\n",
    "                if i == 0:\n",
    "                    dp[i][j][0] = 0\n",
    "                    dp[i][j][1] = -prices[i]\n",
    "                    continue\n",
    "                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]+prices[i])\n",
    "                dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0]-prices[i])\n",
    "\n",
    "        return dp[n-1][k][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        N = len(prices)\n",
    "        # 定义状态:dp[i][j][k]表示在第i天，有j次交易机会，持有或不持有的最大利润\n",
    "        dp = [[[0 for i in range(2)] for j in range(k+1)] for m in range(N)]\n",
    "\n",
    "        for i in range(N):\n",
    "            for j in range(1, k+1):\n",
    "                if i - 1 == -1:\n",
    "                    dp[i][j][0] = 0\n",
    "                    dp[i][j][1] = -prices[i]\n",
    "                else:\n",
    "                    dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])\n",
    "                    dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])\n",
    "\n",
    "        return dp[N-1][k][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        f = [[[-inf] * 2 for _ in range(k+2)] for _ in range(n+1)]\n",
    "\n",
    "        # 边界条件\n",
    "        for j in range(1,k+2):\n",
    "            f[0][j][0] = 0\n",
    "\n",
    "        # 递推：执行转移方程\n",
    "        for i,p in enumerate(prices):\n",
    "            for j in range(1,k+2):\n",
    "                f[i+1][j][0] = max(f[i][j][0], f[i][j][1]+p)\n",
    "                f[i+1][j][1]  =max(f[i][j][1], f[i][j-1][0]-p)\n",
    "        \n",
    "        return f[-1][-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        dp = [[[0, 0] for i in range(k+1)] for j in range(len(prices))]\n",
    "        dp[0][0][1] = -prices[0]\n",
    "        for i in range(1, k + 1):\n",
    "            dp[0][i][0] = float('-inf')\n",
    "            dp[0][i][1] = float('-inf')\n",
    "        for i in range(1, len(prices)):\n",
    "            dp[i][0][1] = max(dp[i-1][0][0]-prices[i], dp[i-1][0][1])\n",
    "            for j in range(1, k+1):\n",
    "                dp[i][j][0] = max(\n",
    "                    dp[i-1][j][0], dp[i-1][j-1][1] + prices[i])\n",
    "                dp[i][j][1] = max(\n",
    "                        dp[i-1][j][1], dp[i-1][j][0] - prices[i])\n",
    "        print(dp)\n",
    "        return max([dp[-1][i][0] for i in range(k+1)]+[dp[-1][i][1] for i in range(k+1)])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        #根据题目长度至少为1，不需要边界判断\n",
    "        if not prices: return 0  \n",
    "\n",
    "        #获取股票的天数，即prices的长度\n",
    "        n = len(prices)\n",
    "        # if n == 0:\n",
    "        #     return 0\n",
    "\n",
    "        #设定一个三位数字，表示第i天，最大交易次数为k，是否持有股票的最大利润\n",
    "        #注意： dp =[ [[0] * 2 for _ in range(k+1)] *(n)] 这么写是不对的，这么写的话k的长度就不对了 [[[0, 0], [0, 0], [0, 0], [0, 0], [0, 0], [0, 0], [0, 0], [0, 0], [0, 0]]] \n",
    "        dp =[ [[0] * 2 for _ in range(k+1)] for _ in range(n)]\n",
    "\n",
    "        # dp = [[[0] * 2 for _ in range( k + 1 )] for _ in range(n)]\n",
    "\n",
    "        print(dp)\n",
    "        #初始化\n",
    "        for j in range(1,k+1):\n",
    "            #第0天结束的时候手上没有股票的最大利润肯定为0\n",
    "            dp[0][j][0] = 0\n",
    "            #第0天结束时，如果买了股票，那最大利润就是第0天的买入价格\n",
    "            dp[0][j][1] = -prices[0]\n",
    "        print(dp)\n",
    "\n",
    "        #遍历股票，计算第i天的最大利润\n",
    "        for i in range(1,n):\n",
    "            #遍历交易次数\n",
    "            for j in range(1,k+1):\n",
    "                #第i天最大交易此时为j，不持有股票的最大利润，不持有股票的情况：卖出或者休息\n",
    "                #不持有股票的话，第i天要么卖出，卖出的话，利润为前一天持有股票时的利润+第i天卖出的金额\n",
    "                #休息的话，前一天肯定也是不持有股票的，利润为前一天不持有股票的利润\n",
    "                dp[i][j][0] = max( dp[i - 1][j][0] , dp[i - 1][j][1] + prices[i] ) \n",
    "\n",
    "                #第i天持有股票的最大利润，持有股票的情况：买入，或者休息\n",
    "                #买入的话，前一天肯定时没有持有股票的，因为（你必须在再次购买前出售掉之前的股票），买入后的利润为前一天不持有的最大利润减去买入的金额\n",
    "                #休息的话，前一天肯定是持有股票的，那也就是前一天持有股票的最大利润\n",
    "                dp[i][j][1] = max( dp[i - 1][j][1] , dp[i - 1][j-1][0] - prices[i] ) \n",
    "        print(dp)\n",
    "\n",
    "        #一直计算，直到最后一天在最大交易次数为k的最大利润，即为当前的最大利润\n",
    "        # return max(dp[n-1][k][0],dp[n-1][k][1])\n",
    "        #其实对于最后一天来说，带着前一天的最大利润来到最后一天，肯定是不执行买入的利润是最大的，因为可以直接返回 dp[n-1][k][0]\n",
    "        return dp[n-1][k][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        dp = [[[float('-inf'),float('-inf')] for _ in range(k)] for _ in range(len(prices))]\n",
    "\n",
    "        for i in range(k):\n",
    "            dp[0][i][0] = -prices[0]\n",
    "            dp[0][i][1] = 0\n",
    "        for i in range(1, len(prices)):\n",
    "            for j in range(k):\n",
    "                if j == 0:\n",
    "                    dp[i][j][0] = max(dp[i-1][j][0], -prices[i])\n",
    "                else:\n",
    "                    dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j-1][1]-prices[i])\n",
    "                dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j][0]+prices[i])\n",
    "\n",
    "        max_p = dp[-1][0][1]\n",
    "        print('max_p',max_p)\n",
    "        for i in range(1,k):\n",
    "            \n",
    "            max_p = max(max_p, dp[-1][i][1])\n",
    "        return max_p\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        dp = [[[-inf for _ in range(2)] for _ in range(k+2)] for _ in range(n+1)]\n",
    "\n",
    "        for j in range(1,k+2):\n",
    "            dp[0][j][0] = 0\n",
    "            \n",
    "        for i,p in enumerate(prices):\n",
    "            for j in range(1,k+2):\n",
    "                dp[i+1][j][0]=max(dp[i][j][0], dp[i][j][1]+p)\n",
    "                dp[i+1][j][1]=max(dp[i][j][1], dp[i][j-1][0]-p)\n",
    "        \n",
    "        return dp[-1][-1][0]\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "        n = len(prices)\n",
    "        f = [[[-inf] * 2 for _ in range(k+2)] for _ in range(n+1)]\n",
    "\n",
    "        # 边界条件\n",
    "        for j in range(1,k+2):\n",
    "            f[0][j][0] = 0\n",
    "\n",
    "        # 递推：执行转移方程\n",
    "        for i,p in enumerate(prices):\n",
    "            for j in range(1,k+2):\n",
    "                f[i+1][j][0] = max(f[i][j][0], f[i][j][1]+p)\n",
    "                f[i+1][j][1]  =max(f[i][j][1], f[i][j-1][0]-p)\n",
    "        \n",
    "        return f[-1][-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        k = min(k, len(prices) // 2)\n",
    "        if k==0:\n",
    "            return 0\n",
    "        tp1,tp2 = [0]*k,[-prices[0]]*k\n",
    "        for p in prices[1:]:\n",
    "            tp2[0] = max(tp2[0],-p)\n",
    "            for i in range(k-1):\n",
    "                tp2[i+1] = max(tp2[i+1],tp1[i]-p)\n",
    "                tp1[i] = max(tp1[i],tp2[i]+p)\n",
    "            tp1[k-1] = max(tp1[k-1],tp2[k-1]+p)           \n",
    "        return tp1[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        import numpy as np\n",
    "        n_days = len(prices)\n",
    "        dp = np.zeros((n_days+1, k+1, 2))\n",
    "        new_price = [0]\n",
    "        new_price.extend(prices)\n",
    "        for i in range(1, k+1):\n",
    "            dp[0][i][1] = -new_price[1]\n",
    "        for i in range(n_days+1):\n",
    "            dp[i][0][1] = -new_price[i]\n",
    "        for day in range(1, n_days+1):\n",
    "            for n_op in range(1, k+1):\n",
    "                dp[day][n_op][0] = max(dp[day-1][n_op][0], dp[day-1][n_op][1]+new_price[day])\n",
    "                dp[day][n_op][1] = max(dp[day-1][n_op-1][0]-new_price[day], dp[day-1][n_op][1])\n",
    "        return int(max(dp[-1,:,0]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        :type k: int\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if k==0:\n",
    "            return 0\n",
    "        if not prices:\n",
    "            return 0\n",
    "        #定义dp[i][k][0/1]表示第i天，最多操作k次时候,卖出/持有股票的总价值\n",
    "        k=2*k\n",
    "        n=len(prices)\n",
    "        dp=[[[0]*2 for _ in range(k+1)] for __ in range(n)]\n",
    "\n",
    "        #初始值,当k=0的时候，dp=0\n",
    "        #当i=0的时候\n",
    "        for j in range(1,k+1):\n",
    "            dp[0][j][0]=0\n",
    "            dp[0][j][1]=-prices[0]\n",
    "\n",
    "        for i in range(1,n):\n",
    "            for j in range(1,k+1):\n",
    "                dp[i][j][0]=max(dp[i-1][j][0], dp[i-1][j-1][1]+prices[i])\n",
    "                dp[i][j][1]=max(dp[i-1][j][1], dp[i-1][j-1][0]-prices[i])\n",
    "        return dp[n-1][k][0]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        n=len(prices)\n",
    "        dp=[[[-float(\"inf\") for _ in range(2)]for _ in range(k+1)]for _ in range(n)]\n",
    "        for i in range(k+1):\n",
    "            dp[0][i][0]=0\n",
    "            dp[0][i][1]=-prices[0]\n",
    "        for i in range(1,n):\n",
    "            for j in range(k+1):\n",
    "                if j==0:\n",
    "                    dp[i][j][0]=0\n",
    "                if j!=0:\n",
    "                    dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j-1][1]+prices[i])\n",
    "                dp[i][j][1]=max(dp[i-1][j][1],dp[i][j][0]-prices[i])\n",
    "        print(dp)\n",
    "        return dp[-1][-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "    n = len(prices)\n",
    "    cache = {i: {} for i in range(n)}\n",
    "\n",
    "    def dfs(i, s):\n",
    "      if i >= n or s == 2 * k: return 0\n",
    "      if s not in cache[i].keys():\n",
    "        if s % 2 == 0:\n",
    "          cache[i][s] = max(dfs(i + 1, s), dfs(i + 1, s + 1) - prices[i])\n",
    "        elif s % 2 == 1:\n",
    "          cache[i][s] = max(dfs(i + 1, s), dfs(i + 1, s + 1) + prices[i])\n",
    "      return cache[i][s]\n",
    "    \n",
    "    return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "    n = len(prices)\n",
    "    cache = {i: {} for i in range(n)}\n",
    "\n",
    "    def dfs(i, s):\n",
    "      if i >= n or s == 2 * k: return 0\n",
    "      if s not in cache[i].keys():\n",
    "        if s % 2 == 0:\n",
    "          cache[i][s] = max(dfs(i + 1, s), dfs(i, s + 1) - prices[i])\n",
    "        elif s % 2 == 1:\n",
    "          cache[i][s] = max(dfs(i + 1, s), dfs(i + 1, s + 1) + prices[i])\n",
    "      return cache[i][s]\n",
    "    \n",
    "    return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        dp = [[[-inf]*(2) for _ in range(2*k+1)] for _ in range(n+1)]\n",
    "        for i in range(n):\n",
    "            dp[i][0][0] = 0\n",
    "        for i in range(n):\n",
    "            for j in range(1, 2*k+1):\n",
    "                dp[i+1][j][0] = max(dp[i][j][0], dp[i][j-1][1] + prices[i])\n",
    "                dp[i+1][j][1] = max(dp[i][j][1], dp[i][j-1][0] - prices[i])\n",
    "        res = 0\n",
    "        for i in range(2*k+1):\n",
    "            res = max(dp[n][i][0], res)\n",
    "            res = max(dp[n][i][1], res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k_: int, prices: List[int]) -> int:\n",
    "        #dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k-1][1]+prices[i-1])\n",
    "        #dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k][1]-prices[i-1])\n",
    "        #dp[0][:][1] = -float('inf')\n",
    "        #dp[:][0][1] = -float('inf')\n",
    "        dp = [[[0, -float('inf')] for k in range(k_ + 1)] for i in range(len(prices)+1)]\n",
    "        \n",
    "        for i in range(1, len(prices)+1):\n",
    "            for k in range(1, k_ + 1):\n",
    "                dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k-1][1]+prices[i-1])\n",
    "                dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k][0]-prices[i-1])\n",
    "        print(dp)\n",
    "        dp = [[[0, -float('inf')] for k in range(k_ + 1)] for i in range(len(prices)+1)]\n",
    "        \n",
    "        for i in range(1, len(prices)+1):\n",
    "            for k in range(1, k_ + 1):\n",
    "                dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1]+prices[i-1])\n",
    "                dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i-1])\n",
    "        print(dp)\n",
    "        \n",
    "        \n",
    "        return dp[-1][-1][0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        dp = dict()\n",
    "        for cnt in range(0, k+1):\n",
    "            for t, p in enumerate(prices):\n",
    "                \n",
    "                if cnt == 0:\n",
    "                    dp[cnt, t] = (0, 0)\n",
    "                elif t == 0:\n",
    "                    dp[cnt, t] = (-p, 0)\n",
    "                else:\n",
    "                    # print(dp)\n",
    "                    s0 = max(dp[cnt, t-1][0], dp[cnt-1, t-1][1]-p)\n",
    "                    s1 = max(dp[cnt, t-1][1], dp[cnt, t-1][0]+p)\n",
    "                    dp[cnt,t] = (s0, s1)\n",
    "        \n",
    "        return dp[(k, t)][1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        def _max_profit(prices):\n",
    "            dp = np.zeros((len(prices), 2), dtype=int).tolist()\n",
    "            dp[0][1] = -prices[0]\n",
    "            for i in range(1, len(prices)):\n",
    "                dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])\n",
    "                dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])\n",
    "            return dp[len(prices)-1][0]\n",
    "        \n",
    "        if k >= len(prices)//2:\n",
    "            return _max_profit(prices)\n",
    "        \n",
    "        dp = np.zeros((len(prices), k+1, 2), dtype=int).tolist()\n",
    "        for i in range(1, k+1):\n",
    "            dp[0][i][1] = -prices[0]\n",
    "        for i in range(1, len(prices)):\n",
    "            for j in range(1, k+1):\n",
    "                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]+prices[i])\n",
    "                dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0]-prices[i])\n",
    "        return dp[len(prices)-1][k][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        dp = {}\n",
    "        n = len(prices)\n",
    "        if n == 0:return 0\n",
    "        max_k = k\n",
    "        for i in range(n):\n",
    "            dp[i] = {}\n",
    "            for k in range(max_k,-1,-1):\n",
    "                dp[i][k] = {}\n",
    "                #base case\n",
    "                if i == 0:\n",
    "                    dp[i][k][0] = 0\n",
    "                    dp[i][k][1] = -prices[i]\n",
    "                    continue\n",
    "                if k == 0:\n",
    "                    dp[i][k][0] = 0\n",
    "                    dp[i][k][1] = float(\"-inf\")\n",
    "                    continue\n",
    "                #状态转移\n",
    "                dp[i][k][0] = max(dp[i-1][k][0],dp[i-1][k][1] + prices[i])\n",
    "                dp[i][k][1] = max(dp[i-1][k][1],dp[i-1][k-1][0] - prices[i])\n",
    "        return dp[n-1][max_k][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, a: List[int]) -> int:\n",
    "        n = len(a) + 1\n",
    "        f = [[[-100000] * 3 for _ in range(k + 1)] for _ in range(n)]\n",
    "        f[0][0][0] = 0\n",
    "        res = 0\n",
    "        # print(numpy.array(f).shape)\n",
    "        for i in range(1, n):\n",
    "            for j in range(0, k + 1):\n",
    "                f[i][j][0] = f[i - 1][j][0]\n",
    "                if j > 0:\n",
    "                    f[i][j][0] = max(f[i][j][0], f[i - 1][j - 1][1] + a[i - 1])\n",
    "                # print(i, j)\n",
    "                f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j][0] - a[i - 1])\n",
    "                res = max(res, f[i][j][0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        c=len(prices)\n",
    "        @cache\n",
    "        def dwjs(p,k):\n",
    "            if p==c or k==0:\n",
    "                return 0\n",
    "            rr,s=0,0\n",
    "            if k==1:\n",
    "                i=prices[p]\n",
    "                for j in range(p,c):\n",
    "                    s=prices[j]-i\n",
    "                    if rr<s:\n",
    "                        rr=s\n",
    "                    if i>prices[j]:\n",
    "                        i=prices[j]\n",
    "                return rr\n",
    "            rr=dwjs(p+1,k)\n",
    "            s=dwjs(p,k-1)\n",
    "            rr=max(rr,s)\n",
    "            i=prices[p]\n",
    "            for j in range(p+1,c-1):\n",
    "                if prices[j]>i:\n",
    "                    s=prices[j]-prices[p]+dwjs(j+1,k-1)\n",
    "                    if s>rr:\n",
    "                        rr=s\n",
    "                    i=prices[j]\n",
    "                if prices[j]<prices[p]:\n",
    "                    break\n",
    "            return rr\n",
    "\n",
    "        ret=dwjs(0,k)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        定义状态：\n",
    "            G[i,j]表示第i天卖出股票，且共进行了j次交易的最大收益。\n",
    "            R[m,n]表示从第m天开始到第i天之间(包含m不包含n)买入一只股票，并在第n天卖出该股票所能获得的最大收获。\n",
    "        转移方程：\n",
    "            根据R[m,n]的定义:\n",
    "                R[m,n] = max{prices[n] - prices[d] for d in range(m,n)} = prices[n] - min{prices[m:n]}\n",
    "            根据G[i,j]的定义，G[i,j]表示第i天完成第j笔交易，则第i天之前的第m天完成了j-1笔交易，第m+1天到第i天买入了一只股票并且第i天进行了卖出。\n",
    "            所以：\n",
    "                G[i,j] = max{G[m,j-1] + R[m+1,i] for m in range(0,i-1)}\n",
    "        边界条件：\n",
    "            G[i,0] = 0\n",
    "            G[i,1] = R[0,i]\n",
    "            G[i,j] = -inf  if j>(i+1)//2， 因为第i天最多只能进行(i+1)//2笔交易,因为完成一笔交易至少需要两天时间。\n",
    "        返回：\n",
    "            G.max()\n",
    "        \"\"\"\n",
    "\n",
    "        N = len(prices)\n",
    "        #首先计算R，表征在一段时间内完成一笔交易所能获得的最大收益。\n",
    "        R = np.zeros([N,N],dtype=np.int64)\n",
    "        for m in range(N-1):\n",
    "            for n in range(m+1,N):\n",
    "                R[m,n] = prices[n] - min(prices[m:n])\n",
    "        #计算G\n",
    "        INF: int = int(10000)\n",
    "        G = -1*INF*np.ones([N,k+1], dtype=np.int64)\n",
    "        G[:,0] = 0\n",
    "        G[1:,1] = R[0,1:]\n",
    "        for i in range(N):\n",
    "            max_j = min((i+1) // 2, k) #i+1表示index=i的日期实际上是第i+1天，因为日期index从0开始。第i+1天最多允许进行i+1 // 2笔交易\n",
    "            for j in range(2,1+max_j):\n",
    "                min_m = 2*j-3 #要完成j-1笔交易最少需要2*(j-1)天，其日期的index=2*(j-1)-1 = 2*j-3\n",
    "                G[i,j] = (G[min_m:i-1,j-1] + R[min_m+1:i,i]).max()\n",
    "        return int(G.max())\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=188 lang=python3\n",
    "#\n",
    "# [188] 买卖股票的最佳时机 IV\n",
    "#\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        self._cache = {}\n",
    "        self._prices = prices\n",
    "        k = min(k, len(prices) // 2)\n",
    "        return max(self._max_profit(len(prices) - 1, k, True), self._max_profit(len(prices) - 1, k, False))\n",
    "    \n",
    "    def _max_profit(self, index, k, has_stock):\n",
    "        cache_key = f'{index}_{k}_{has_stock}'\n",
    "        if cache_key in self._cache:\n",
    "            return self._cache[cache_key]\n",
    "        \n",
    "        if k <= 0 or not self._prices:\n",
    "            profit = 0\n",
    "        elif index <= 0:\n",
    "            profit = 0 if not has_stock else -self._prices[0]\n",
    "        elif has_stock:\n",
    "            profit = max(self._max_profit(index-1, k, True), self._max_profit(index-1, k-1, False) - self._prices[index])\n",
    "        else:\n",
    "            profit = max(self._max_profit(index-1, k, False), self._max_profit(index-1, k, True) + self._prices[index])\n",
    "        \n",
    "        self._cache[cache_key] = profit\n",
    "        return profit\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        dp = defaultdict(lambda: float('-inf'))\n",
    "        n = len(prices)\n",
    "        k = min(n // 2, k)\n",
    "\n",
    "        # bound\n",
    "        dp[(0, 0, \"buy\")] = -prices[0]\n",
    "        for i in range(1, n):\n",
    "            dp[(i, 0, \"buy\")] = max(dp[(i-1, 0, \"buy\")], -prices[i])\n",
    "\n",
    "        # iteration                                                  0 buy 1 sell 1 buy \n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, k+1):\n",
    "                dp[(i, j, \"sell\")] = max( dp[(i-1, j, \"sell\")], dp[(i-1, j-1,  \"buy\")] + prices[i])\n",
    "                dp[(i, j,  \"buy\")] = max( dp[(i-1, j,  \"buy\")], dp[(i-1,   j, \"sell\")] - prices[i])\n",
    "                ans = max(ans, dp[(i, j, \"sell\")], dp[(i, j, \"buy\")])\n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        INF = 10 ** 10\n",
    "\n",
    "        prices = [prices[0]] + [prices[i] for i in range(1, len(prices)) if prices[i] != prices[i-1]]\n",
    "        keep = [prices[i] for i in range(1, len(prices) - 1) if (prices[i-1] < prices[i]) != (prices[i] < prices[i+1])]\n",
    "        prices = [prices[0]] + keep + [prices[-1]]\n",
    "        if len(prices) >= 2 and prices[-1] < prices[-2]:\n",
    "            prices.pop()\n",
    "        if len(prices) >= 2 and prices[0] > prices[1]:\n",
    "            prices.pop(0)\n",
    "        if len(prices) < 2:\n",
    "            return 0\n",
    "        assert len(prices) % 2 == 0\n",
    "\n",
    "        valleys = prices[::2]\n",
    "        peaks = prices[1::2]\n",
    "\n",
    "        @cache\n",
    "        def f(i, j, l):\n",
    "            if i == len(peaks):\n",
    "                return 0\n",
    "            if j <= 0:\n",
    "                return 0\n",
    "            res = f(i + 1, j, min(l, valleys[i]))\n",
    "            res = max(res, peaks[i] - min(l, valleys[i]) + f(i + 1, j - 1, INF))\n",
    "            # print(i, j, l, res)\n",
    "            return res\n",
    "\n",
    "        res = f(0, k, INF)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.prices = None\n",
    "        self.memo_dict = {}\n",
    "    def dp(self,n,k,is_buy):\n",
    "        if (n,k,is_buy) in self.memo_dict:\n",
    "            return self.memo_dict.get((n,k,is_buy))\n",
    "        # base case\n",
    "        if k == 0:\n",
    "            return 0    \n",
    "        if n == 0:\n",
    "            return 0\n",
    "\n",
    "        # choice\n",
    "        res = 0\n",
    "        if is_buy == 0:\n",
    "            res = max(res,self.dp(n-1,k,0),self.dp(n-1,k,1)-self.prices[len(self.prices)-n])\n",
    "        else:\n",
    "            res = max(res,self.dp(n-1,k,1),self.dp(n-1,k-1,0)+self.prices[len(self.prices)-n])\n",
    "        self.memo_dict[(n,k,is_buy)] = res\n",
    "        return res\n",
    "\n",
    "    def maxProfit(self, k, prices):\n",
    "        self.prices = prices\n",
    "        return self.dp(len(prices),k,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        dp = defaultdict(int)\n",
    "        for cnt in range(0, k+1):\n",
    "            for t, p in enumerate(prices):\n",
    "                if t == 0:\n",
    "                    dp[cnt, t, 0] = -p\n",
    "                elif cnt>0:\n",
    "                    # print(dp)\n",
    "                    dp[cnt,t, 0] = max(dp[cnt, t-1, 0], dp[cnt-1, t-1, 1]-p)\n",
    "                    dp[cnt,t, 1] = max(dp[cnt, t-1, 1], dp[cnt, t-1, 0]+p)\n",
    "        \n",
    "        return dp[k, t, 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        dp = {}\n",
    "        # bound \n",
    "        n = len(prices)\n",
    "        dp[(0, 0, \"buy\")] = -prices[0]\n",
    "        for i in range(1, n):\n",
    "            dp[(i, 0, \"buy\")] = max(dp[(i-1, 0, \"buy\")], -prices[i])\n",
    "        for i in range(1, k+1):\n",
    "            dp[(0, i, \"buy\")] = float('-inf')\n",
    "\n",
    "        dp[(0, 0, \"sell\")] = 0\n",
    "        for i in range(1, n):\n",
    "            dp[(i, 0, \"sell\")] = 0\n",
    "        for i in range(1, k+1):\n",
    "            dp[(0, i, \"sell\")] = float('-inf')\n",
    "\n",
    "\n",
    "        # iteration\n",
    "        # 0 buy 1 sell ...  k sell k buy\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, k+1):\n",
    "                dp[(i, j, \"sell\")] = max(dp[(i-1, j-1,  \"buy\")] + prices[i], dp[(i-1, j, \"sell\")]) \n",
    "                dp[(i, j,  \"buy\")] = max(dp[(i-1,   j, \"sell\")] - prices[i], dp[(i-1, j, \"buy\")]) \n",
    "                ans = max(ans, dp[(i, j,  \"buy\")], dp[(i, j,  \"sell\")])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        global max_pro\n",
    "        max_pro ={}\n",
    "        def dpprofit(prices,transaction,hold,ind,cash):\n",
    "\n",
    "            future_pro =max_pro.get((transaction,hold,ind))\n",
    "            if future_pro:\n",
    "                return future_pro\n",
    "\n",
    "            if ind ==len(prices) or transaction==0:\n",
    "                return 0\n",
    "            no_bevior = dpprofit(prices,transaction,hold,ind+1,cash)\n",
    "            if not hold:\n",
    "                buying =  -prices[ind]+ dpprofit(prices,transaction,not hold,ind+1,cash-prices[ind])\n",
    "                max_pro[(transaction,hold,ind)]=max(no_bevior,buying)\n",
    "                return max(no_bevior,buying)\n",
    "            else:\n",
    "                selling = prices[ind]+dpprofit(prices,transaction-1,not hold,ind+1,cash+prices[ind])\n",
    "                max_pro[(transaction,hold,ind)]=max(no_bevior,selling)\n",
    "                return max(no_bevior,selling)\n",
    "\n",
    "        return dpprofit(prices,k,False,0,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        self.dict = {}\n",
    "        self.prices = prices\n",
    "        re = 0\n",
    "        for i in range(len(prices)):\n",
    "            re = max(re,self.dp(i,False,k))\n",
    "        return re\n",
    "    \n",
    "    def dp(self,i,zhuangtai,jiaoyicishu):\n",
    "        if (i,zhuangtai,jiaoyicishu) in self.dict:\n",
    "            return self.dict[(i,zhuangtai,jiaoyicishu)]\n",
    "        if i==len(self.prices):\n",
    "            self.dict[(i,zhuangtai,jiaoyicishu)] = 0\n",
    "            return 0\n",
    "        if jiaoyicishu>0:\n",
    "            if zhuangtai:\n",
    "                re1 = self.dp(i+1,False,jiaoyicishu-1)+self.prices[i]\n",
    "                re2 = self.dp(i+1,True,jiaoyicishu)\n",
    "                self.dict[(i,zhuangtai,jiaoyicishu)] = max(re1,re2)\n",
    "                return max(re1,re2)\n",
    "            else:\n",
    "                re1 = self.dp(i+1,False,jiaoyicishu)\n",
    "                re2 = self.dp(i+1,True, jiaoyicishu)-self.prices[i]\n",
    "                self.dict[(i,zhuangtai,jiaoyicishu)] = max(re1,re2)\n",
    "                return max(re1,re2)\n",
    "        elif jiaoyicishu==0:\n",
    "            self.dict[(i,zhuangtai,jiaoyicishu)] = 0\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxProfit(self, k, prices):\n",
    "        \n",
    "        @cache\n",
    "        def dfs(index, remain, hold):\n",
    "            if remain == 0:\n",
    "                return 0\n",
    "            \n",
    "            if index == len(prices):\n",
    "                return 0\n",
    "\n",
    "            results = []\n",
    "            price = prices[index]\n",
    "\n",
    "            if hold:\n",
    "                # sell and buy\n",
    "                results += [dfs(index + 1, remain - 1, True)]\n",
    "                # sell and not buy\n",
    "                results += [dfs(index + 1, remain - 1, False) + price]\n",
    "                # not sell and not buy\n",
    "                results += [dfs(index + 1, remain, True)]\n",
    "            else:\n",
    "                # buy\n",
    "                results += [dfs(index + 1, remain, True) - price]\n",
    "                # not buy\n",
    "                results += [dfs(index + 1, remain, False)]\n",
    "            \n",
    "            return max(results)\n",
    "        \n",
    "        return dfs(0, k, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def dfs(prices,index,k,flag,map):\n",
    "    if (index,k,flag) in map:\n",
    "        return map[index,k,flag]\n",
    "    if index>=len(prices):\n",
    "        return 0\n",
    "    \n",
    "    if k ==0:\n",
    "        return 0\n",
    "    way1,way2 = 0,0\n",
    "    if flag:\n",
    "        way1 = dfs(prices,index,k-1,not flag,map)+prices[index]\n",
    "        way2 = dfs(prices,index+1,k,flag,map)\n",
    "    else:\n",
    "        way1 = dfs(prices,index,k,not flag,map)-prices[index]\n",
    "        way2 = dfs(prices,index+1,k,flag,map)\n",
    "    res = max(way1,way2)\n",
    "    map[index,k,flag] = res\n",
    "    return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        return dfs(prices,0,k,False,{})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, hold, remain):  # buy+sell = 1 transaction\n",
    "            if remain < 0:  # invalid\n",
    "                return float('-inf')\n",
    "            if idx == len(prices):  # no more stock\n",
    "                return 0\n",
    "            if hold:  # hold stock now\n",
    "                sell = dfs(idx + 1, False, remain - 1) + prices[idx]\n",
    "                not_sell = dfs(idx + 1, True, remain)\n",
    "                return max(sell, not_sell)\n",
    "            else:  # not hold stock now\n",
    "                buy = dfs(idx + 1, True, remain) - prices[idx]\n",
    "                not_buy = dfs(idx + 1, False, remain)\n",
    "                return max(buy, not_buy)\n",
    "        \n",
    "        return dfs(0, False, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def maxProfit(self, k, prices):\n",
    "        \"\"\"\n",
    "        :type k: int\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.prices = prices\n",
    "        if k >= len(prices) // 2:\n",
    "            k = float('inf')\n",
    "        return self.res(len(prices)-1, k, 0)\n",
    "\n",
    "    @lru_cache(None)\n",
    "    def res(self, i, k, hold):\n",
    "        \"\"\"\n",
    "        k: 剩余买入次数.\n",
    "        \"\"\"\n",
    "        if i < 0 and hold:\n",
    "            return float('-inf')\n",
    "        elif i < 0 and (not hold):\n",
    "            return 0\n",
    "        if k <= 0:\n",
    "            return 0\n",
    "\n",
    "        # 手上有股票\n",
    "        if hold:\n",
    "            return max(\n",
    "                self.res(i-1, k, 1),\n",
    "                self.res(i-1, k-1, 0) - self.prices[i]\n",
    "            )\n",
    "        # 手上没股票\n",
    "        else:\n",
    "            return max(\n",
    "                self.res(i-1, k, 1) + self.prices[i],\n",
    "                self.res(i-1, k, 0)\n",
    "            )\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        if len(prices) < 2:\n",
    "            return 0\n",
    "        \n",
    "        n = len(prices)\n",
    "        k = min(k,n//2)\n",
    "        \n",
    "        # 第i天,j次交易,l是否持仓\n",
    "        # i,j,1 = max([i-1,j,1],[i-1,j,0]-price[i]) 买入要么是持有过来的，要么是现场买入的\n",
    "        # i,j,0 = max([i-1,j,0],[i-1,j-1,1] + price[i]) 要么是持有的，要么是卖出的\n",
    "\n",
    "        dp = defaultdict(lambda:defaultdict(lambda:defaultdict(lambda:0)))\n",
    "\n",
    "        dp[0][0][0] = 0\n",
    "        dp[0][0][1] = -prices[0]\n",
    "\n",
    "        for i in range(1,n):\n",
    "            dp[i][0][0] = 0\n",
    "            dp[i][0][1] = max(-prices[i],dp[i-1][0][1])\n",
    "        \n",
    "        for j in range(1,k+1):\n",
    "            dp[0][j][0] = 0\n",
    "            dp[0][j][1] = -prices[0]\n",
    "\n",
    "        for j in range(1,k+1):\n",
    "            for i in range(1,n):\n",
    "                dp[i][j][0] = max(dp[i-1][j][0],dp[i-1][j-1][1]+prices[i])\n",
    "                dp[i][j][1] = max(dp[i-1][j][1],dp[i-1][j][0]-prices[i])\n",
    "                #print(i,j,0,'|',dp[i][j][0])\n",
    "                #print(i,j,1,'|',dp[i][j][1])\n",
    "        \n",
    "        return dp[n-1][k][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        if prices == []: return 0\n",
    "        lst = []\n",
    "        min_price = max_price = prices[0]\n",
    "        for price in prices:\n",
    "            if price > max_price:\n",
    "                max_price = price\n",
    "            else:\n",
    "                if max_price > min_price:\n",
    "                    lst.append((min_price, max_price))\n",
    "                min_price = max_price = price\n",
    "        if max_price > min_price:\n",
    "            lst.append((min_price, max_price))\n",
    "        if lst == []:\n",
    "            return 0\n",
    "        @cache\n",
    "        def getMax(lst, k):\n",
    "            if k == 0: return 0\n",
    "            if len(lst) <= k: return sum(x[1]-x[0] for x in lst)\n",
    "            m, M = lst[0]\n",
    "            ans = M-m\n",
    "            max_till = M-m\n",
    "            for i in range(len(lst)-k+1):\n",
    "                new_min, new_max = lst[i]\n",
    "                if new_min < m:\n",
    "                    m = new_min\n",
    "                    M = new_max\n",
    "                elif new_max > M: M = new_max\n",
    "                if M-m > max_till: max_till = M-m\n",
    "                ans = max(ans, max_till+getMax(lst[i+1:], k-1))\n",
    "            return ans\n",
    "        return getMax(tuple(lst),k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        from functools import lru_cache\n",
    "        @lru_cache(1000000)\n",
    "        def dfs(i, cnt, on):\n",
    "            if cnt < 0:\n",
    "                return -int(1e9 + 7)\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            if i == 0:\n",
    "                return 0 if on else (-prices[0] if cnt > 0 else -int(1e9 + 7))\n",
    "            if on:\n",
    "                return max(dfs(i - 1, cnt, on), dfs(i - 1, cnt, not on) + prices[i])\n",
    "            else:\n",
    "                return max(dfs(i - 1, cnt, on), dfs(i - 1, cnt - 1, not on) - prices[i])\n",
    "        return dfs(len(prices) - 1, k, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        size=len(prices)\n",
    "        @functools.cache\n",
    "        def dfs(idx,mark,cont):\n",
    "            if cont==k:return 0\n",
    "            if mark==2:\n",
    "                mark=0\n",
    "            if idx==size:return 0\n",
    "            \n",
    "            if mark==0:ans=max(dfs(idx+1,mark+1,cont)-prices[idx],dfs(idx+1,mark,cont))\n",
    "            if mark==1:ans=max(dfs(idx+1,mark+1,cont+1)+prices[idx],dfs(idx+1,mark,cont))\n",
    "\n",
    "            return ans\n",
    "\n",
    "        return dfs(0,0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: [int]) -> int:\n",
    "        flag = True if k >= len(prices)//2+1 else False\n",
    "        @lru_cache(None)\n",
    "        def dp(i, k, hold=False):\n",
    "            if i == len(prices) or k == 0:\n",
    "                return 0\n",
    "            if hold:\n",
    "                if flag:\n",
    "                    return max(dp(i+1, k, False)+prices[i], dp(i+1, k, True))\n",
    "                ##########   卖出  #################### 保持   ######\n",
    "                return max(dp(i+1, k-1, False)+prices[i], dp(i+1, k, True))\n",
    "            else:\n",
    "                ##########   卖入  #################### 保持   ######\n",
    "                return max(dp(i+1, k, True)-prices[i], dp(i+1, k, False))\n",
    "        return dp(0, k, False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k:int, prices: List[int]) -> int:\n",
    "        mem={}\n",
    "        def dfs(index,status):\n",
    "            if index==len(prices) or status==2*k: return 0\n",
    "            if status%2==0:\n",
    "                if not mem.__contains__(str(index+1)+\" \"+str(status)):\n",
    "                    mem[str(index+1)+\" \"+str(status)]=dfs(index+1,status)\n",
    "                if not mem.__contains__(str(index+1)+\" \"+str(status+1)):\n",
    "                    mem[str(index+1)+\" \"+str(status+1)]=dfs(index,status+1) \n",
    "                mem[str(index)+\" \"+str(status)]=max(mem[str(index+1)+\" \"+str(status)],mem[str(index+1)+\" \"+str(status+1)]-prices[index])\n",
    "                return mem[str(index)+\" \"+str(status)]\n",
    "            if not mem.__contains__(str(index+1)+\" \"+str(status)):\n",
    "                mem[str(index+1)+\" \"+str(status)]=dfs(index+1,status)\n",
    "            mem[str(index)+\" \"+str(status)]=max(mem[str(index+1)+\" \"+str(status)],dfs(index+1,status+1)+prices[index])\n",
    "            return mem[str(index)+\" \"+str(status)]\n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        n=len(prices)\n",
    "        @cache\n",
    "        def dfs(i,j,hold):\n",
    "            #i 表示天数\n",
    "            #j 表示交易次数\n",
    "            #hold 表示上一轮的状态 True不一定是持有 False也不一定是卖出 看这轮hold是否等于上一轮的hold  因为flase=false也等于True\n",
    "            if j<0:\n",
    "                return -inf\n",
    "            if i<0:\n",
    "                return -inf if hold else 0 #如果持有 返回初始状态 负无穷 不持有 返回0 利润为0\n",
    "            if hold:\n",
    "                #如果上一轮是持有，这轮要么不动  要么买入\n",
    "                return max(dfs(i-1,j,True),dfs(i,j,False)-prices[i])  #上一轮是True True=True 保持上一轮 不保持 买入 增加成本\n",
    "            else:\n",
    "                #如果上一轮是未持有，那可以选择保持不动，要么卖出\n",
    "                return max(dfs(i-1,j,False),dfs(i,j-1,True)+prices[i])\n",
    "        return dfs(n-1,k,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        @cache\n",
    "        def opt_buy(i,k): # max profit from buying at most k times, and selling at most k-1 times, on prices[0...i]. (whatever the number of transactions it is (at most k-1), we know the number of buys is greater than it by 1, as we end on a buy for sure)\n",
    "            return -inf if i == -1 else max(opt_buy(i-1,k), dp(i-1,k-1) - prices[i])\n",
    "\n",
    "        @cache\n",
    "        def dp(i,k): # max profit by at most k transactions on prices[0...i] (transaction = buy and then sell on a subsequent day)\n",
    "            return 0 if i <= 0 or k == 0 else max(dp(i-1,k), opt_buy(i-1,k) + prices[i])\n",
    "        return dp(len(prices)-1,k)\n",
    "\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        # works too... redefine k: to be k FULL transactions in opt_buy...\n",
    "        @cache\n",
    "        def opt_buy(i,k): \n",
    "            return -inf if i == -1 or k == -1 else max(opt_buy(i-1,k), dp(i-1,k) - prices[i])\n",
    "\n",
    "        @cache\n",
    "        def dp(i,k):\n",
    "            return 0 if i <= 0 or k == 0 else max(dp(i-1,k), opt_buy(i-1,k-1) + prices[i])\n",
    "        return dp(len(prices)-1,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        @cache\n",
    "        def dfs(i,s):\n",
    "            if i > n-1 or s == 2*k:\n",
    "                return 0\n",
    "            if s %2 == 0:\n",
    "                ans = max(dfs(i+1,s),dfs(i+1,s+1)-prices[i])\n",
    "            if s %2 != 0:\n",
    "                ans = max(dfs(i+1,s),dfs(i,s+1)+prices[i])\n",
    "            return ans\n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices) -> int:\n",
    "        buy_dict = {}\n",
    "        sell_dict = {}\n",
    "\n",
    "        def buy(i,j):\n",
    "            if (i,j) in buy_dict:\n",
    "                pass\n",
    "            elif j == 0:\n",
    "                buy_dict[(i,j)] = float('-inf')\n",
    "            elif i == 0:\n",
    "                buy_dict[(i,j)] = -prices[0]\n",
    "            else:\n",
    "                buy_dict[(i,j)] = max(buy(i-1,j),sell(i-1,j-1)-prices[i])\n",
    "\n",
    "            return buy_dict[(i,j)]\n",
    "\n",
    "        def sell(i,j):\n",
    "            if (i,j) in sell_dict:\n",
    "                pass\n",
    "            elif i == 0:\n",
    "                sell_dict[(i,j)]=0\n",
    "            else:\n",
    "                sell_dict[(i,j)]=max(sell(i-1,j),buy(i-1,j)+prices[i])\n",
    "            return sell_dict[(i,j)]\n",
    "        res = 0\n",
    "        for j in range(1,k+1):\n",
    "            res  = max(res,sell(len(prices)-1,j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        N=len(prices)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,hold,left):\n",
    "            if left<0:\n",
    "                return -10**9\n",
    "            if i<0:\n",
    "                return 0 if hold==0 else -10**9\n",
    "            if hold:\n",
    "                cur=max(dfs(i-1,1,left),dfs(i-1,0,left)-prices[i])\n",
    "            else:\n",
    "                cur=max(dfs(i-1,0,left),dfs(i-1,1,left-1)+prices[i])\n",
    "            return cur\n",
    "        return dfs(N-1,0,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, k: int, prices: List[int]) -> int:\n",
    "        n: int = len(prices)\n",
    "        @cache\n",
    "        def dfs(i: int, j: int, hold: int) -> int:\n",
    "            if j < 0:\n",
    "                return -inf\n",
    "            if i < 0:\n",
    "                if hold == 1:\n",
    "                    return -inf\n",
    "                else:\n",
    "                    return 0\n",
    "            if hold == 1:\n",
    "                return max(dfs(i - 1, j, 1), dfs(i - 1, j - 1, 0) - prices[i])\n",
    "            return max(dfs(i - 1, j, 0), dfs(i - 1, j, 1) + prices[i])\n",
    "        return dfs(n - 1, k, 0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
